Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs Shi Li This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-7060672/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 7 You are reading this latest preprint version Abstract We revisit the unrelated machine scheduling problem with the weighted completion time objective. It is known that independent rounding achieves a 1.5 approximation for the problem, and many prior algorithms improve upon this ratio by leveraging strong negative correlation schemes. On each machine $i$, these schemes introduce strong negative correlation between events that some pairs of jobs are assigned to $i$, while maintaining non-positive correlation for all pairs. Our algorithm deviates from this methodology by relaxing the pairwise non-positive correlation requirement. On each machine $i$, we identify many groups of jobs. For a job $j$ and a group $B$ not containing $j$, we only enforce non-positive correlation between $j$ and the group as a whole, allowing $j$ to be positively-correlated with individual jobs in $B$. This relaxation suffices to maintain the 1.5-approximation, while enabling us to obtain a much stronger negative correlation within groups using an iterative rounding procedure: at most one job from each group is scheduled on $i$. We prove that the algorithm achieves a $(1.36 + \epsilon)$-approximation, improving upon the previous best approximation ratio of $1.4$ due to Harris. While the improvement may not be substantial, the significance of our contribution lies in the relaxed non-positive correlation condition and the iterative rounding framework. Due to the simplicity of our algorithm, we are able to derive a closed form for the weighted completion time our algorithm achieves with a clean analysis. Unfortunately, we could not provide a good analytical analysis for the quantity; instead, we rely on a computer assisted proof. Nevertheless, the checking algorithm for the analysis is easy to implement, essentially involving evaluation of maximum values of single-variable quadratic functions over given intervals. Therefore, unlike previous results which use intricate analysis to optimize the final approximation ratio, we delegate this task to computer programs. Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviewers agreed at journal 05 Mar, 2026 Reviews received at journal 17 Nov, 2025 Reviewers agreed at journal 16 Jul, 2025 Reviewers invited by journal 16 Jul, 2025 Editor assigned by journal 10 Jul, 2025 Submission checks completed at journal 07 Jul, 2025 First submitted to journal 06 Jul, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-7060672","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":486592294,"identity":"654899f9-33cf-4f7c-8f34-fe855ed8318e","order_by":0,"name":"Shi Li","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAt0lEQVRIiWNgGAWjYDACCcbGAwkVDMxgNrFaGg4knCFNCwPDAcY2OJsIID+7ueHAw3l32A0OMB+8zcNgl0dQi8Gdgw0HErc9YzY4wJZszcOQXExYi0QiSMthoBYeM2kehgOJDQQdNgOkZQ5IC/834rQw3ABpaQDbwkacFgOQloRjh5klD7MZW84xSCbGYekPH/6oOZzMd7z54Y03FXZEOAwKkiGRaUCseiCwI0HtKBgFo2AUjDQAAA8ZP2XOo2s0AAAAAElFTkSuQmCC","orcid":"","institution":"Nanjing University","correspondingAuthor":true,"prefix":"","firstName":"Shi","middleName":"","lastName":"Li","suffix":""}],"badges":[],"createdAt":"2025-07-07 02:53:19","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-7060672/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-7060672/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":87168786,"identity":"58925964-b7c4-48aa-b757-fd436d396e0b","added_by":"auto","created_at":"2025-07-21 06:59:55","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":493037,"visible":true,"origin":"","legend":"","description":"","filename":"submission.pdf","url":"https://assets-eu.researchsquare.com/files/rs-7060672/v1_covered_6926ee41-cf52-4ea1-9af8-9a86f3284270.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"","lastPublishedDoi":"10.21203/rs.3.rs-7060672/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-7060672/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"We revisit the unrelated machine scheduling problem with the weighted completion time objective. It is known that independent rounding achieves a 1.5 approximation for the problem, and many prior algorithms improve upon this ratio by leveraging strong negative correlation schemes. On each machine $i$, these schemes introduce strong negative correlation between events that some pairs of jobs are assigned to $i$, while maintaining non-positive correlation for all pairs. \n\nOur algorithm deviates from this methodology by relaxing the pairwise non-positive correlation requirement. On each machine $i$, we identify many groups of jobs. For a job $j$ and a group $B$ not containing $j$, we only enforce non-positive correlation between $j$ and the group as a whole, allowing $j$ to be positively-correlated with individual jobs in $B$. This relaxation suffices to maintain the 1.5-approximation, while enabling us to obtain a much stronger negative correlation within groups using an iterative rounding procedure: at most one job from each group is scheduled on $i$. \n\nWe prove that the algorithm achieves a $(1.36 + \\epsilon)$-approximation, improving upon the previous best approximation ratio of $1.4$ due to Harris. While the improvement may not be substantial, the significance of our contribution lies in the relaxed non-positive correlation condition and the iterative rounding framework. Due to the simplicity of our algorithm, we are able to derive a closed form for the weighted completion time our algorithm achieves with a clean analysis. Unfortunately, we could not provide a good analytical analysis for the quantity; instead, we rely on a computer assisted proof. Nevertheless, the checking algorithm for the analysis is easy to implement, essentially involving evaluation of maximum values of single-variable quadratic functions over given intervals. Therefore, unlike previous results which use intricate analysis to optimize the final approximation ratio, we delegate this task to computer programs.\n","manuscriptTitle":"Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-07-21 06:51:50","doi":"10.21203/rs.3.rs-7060672/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"reviewerAgreed","content":"312149157097709398625569676521432078823","date":"2026-03-06T03:26:44+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-11-17T17:57:08+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"212035339618241570632868591485420055516","date":"2025-07-17T01:45:31+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-07-16T17:04:25+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-07-10T15:04:30+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-07-07T06:03:13+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithmica","date":"2025-07-07T02:50:05+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"b84acafe-1de2-4357-8ca9-6f918dc2a7e8","owner":[],"postedDate":"July 21st, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2025-07-21T06:51:50+00:00","versionOfRecord":[],"versionCreatedAt":"2025-07-21 06:51:50","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-7060672","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-7060672","identity":"rs-7060672","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}