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

作者：Shi Li · 发表于：Society for Industrial and Applied Mathematics eBooks · 年份：2025 · DOI：10.1137/1.9781611978322.17 · 被引用次数：3 · 研究领域：Advanced Numerical Analysis Techniques、Robotic Mechanisms and Dynamics

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.