Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
<|reference_start|>Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs: 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.<|reference_end|>
@article{li2024approximating,
    title={Approximating Unrelated Machine Weighted Completion Time Using Iterative
  Rounding and Computer Assisted Proofs},
    author={Shi Li},
    journal={arXiv preprint arXiv:2404.04773},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.04773},
    primaryClass={cs.DS}
}