Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00453-008-9251-6 | European Symposium on Algorithms |
Keywords | DocType | Volume |
algorithms · scheduling · vertex cover,series parallel,scheduling problem,vertex cover,partial order | Journal | 53 |
Issue | ISSN | ISBN |
4 | 0178-4617 | 3-540-38875-3 |
Citations | PageRank | References |
20 | 1.12 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |