期刊
JOURNAL OF THE ACM
卷 48, 期 2, 页码 206-242出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/375827.375840
关键词
algorithms; theory; approximation algorithms; convex optimization; performance guarantee; randomized algorithms; scheduling theory; unrelated machines; worst-case ratio
We consider the problem of scheduling unrelated parallel machines subject to release dates so as to minimize the total weighted completion time of jobs. The main contribution of this paper is a provably good convex quadratic programming relaxation of strongly polynomial size For this problem. The best previously known approximation algorithms are based on LP relaxations in time-or interval-indexed variables. Those LP relaxations, however, suffer from a huge number of variables. As a result of the convex quadratic programming approach we can give a very simple and easy to analyze 2-approximation algorithm which can be further improved to performance guarantee 3/2 in the absence of release dates. We also consider preemptive scheduling problems and derive approximation algorithms and results on the power of preemption which improve upon the best previously known results for these settings. Finally, for the special case of two machines we introduce a more sophisticated semidefinite programming relaxation and apply the random hyperplane technique introduced by Goemans and Williamson for the MAXCUT. problem: this leads to an improved 1.2752-approximation.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据