Paper doi abstract bibtex

In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.

@article{ambuhl_single_2008, title = {Single {Machine} {Precedence} {Constrained} {Scheduling} {Is} a {Vertex} {Cover} {Problem}}, volume = {53}, issn = {0178-4617, 1432-0541}, url = {http://link.springer.com/article/10.1007/s00453-008-9251-6}, doi = {10.1007/s00453-008-9251-6}, abstract = {In this paper we study the single machine precedence constrained scheduling problem of minimizing the sum of weighted completion time. Specifically, we settle an open problem first raised by Chudak and Hochbaum and whose answer was subsequently conjectured by Correa and Schulz. As shown by Correa and Schulz, the proof of this conjecture implies that the addressed scheduling problem is a special case of the vertex cover problem. This means that previous results for the scheduling problem can be explained, and in some cases improved, by means of vertex cover theory. For example, the conjecture implies the existence of a polynomial time algorithm for the special case of two-dimensional partial orders. This considerably extends Lawler’s result from 1978 for series-parallel orders.}, language = {en}, number = {4}, urldate = {2015-04-29TZ}, journal = {Algorithmica}, author = {Ambühl, Christoph and Mastrolilli, Monaldo}, month = nov, year = {2008}, keywords = {Algorithm Analysis and Problem Complexity, Computer Systems Organization and Communication Networks, Data Structures, Cryptology and Information Theory, Mathematics of Computing, Theory of Computation, Vertex cover, algorithms, scheduling}, pages = {488--503} }

Downloads: 0