Name
Abstract | ||
|---|---|---|
This paper investigates the relationship between the dimension theory of partial orders and the problem of scheduling precedence-constrained jobs on a single machine to minimize the weighted completion time. Surprisingly, we show that the vertex cover graph associated to the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory. This equivalence gives new insights on the structure of the problem and allows us to benefit from known results in dimension theory. In particular, the vertex cover graph associated to the scheduling problem can be colored efficiently with at most k colors whenever the associated poset admits a polynomial time computable k-realizer. Based on this approach, we derive new and better approximation algorithms for special classes of precedence constraints, including convex bipartite and semi-orders, for which we give $(1+\frac{1}{3})$-approximation algorithms. Our technique also generalizes to a richer class of posets obtained by lexicographic sum. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11830924_4 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
vertex cover graph,dimension theory,associated poset,precedence-constrained single machine scheduling,approximation algorithm,convex bipartite,polynomial time computable k-realizer,new insight,weighted completion time,better approximation algorithm,scheduling problem,combinatorial optimization,col,vertex graph,scheduling,partial order,vertex cover,constrained optimization,lexicography,polynomial time,graph theory,partial ordering | Graph theory,Discrete mathematics,Approximation algorithm,Single-machine scheduling,Combinatorics,Vertex (graph theory),Edge cover,Bipartite graph,Vertex cover,Feedback vertex set,Mathematics | Conference |
Volume | ISSN | ISBN |
4110 | 0302-9743 | 3-540-38044-2 |
Citations | PageRank | References |
7 | 0.51 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |
| Ola Svensson | 3 | 349 | 36.31 |