Name
Abstract | ||
|---|---|---|
We consider the single machine scheduling problem to minimize the average weighted completion time under precedence constrains. Improving on the various 2-approximation algorithms is considered one of the ten most prominent open problems in scheduling theory. Recently, research has focused on special cases of the problem, mostly by restricting the set of precedence constraints to special classes such as convex bipartite, two-dimensional, and interval orders.In this paper we extend our previous results by presenting a framework for obtaining (2 茂戮驴 2/d)-approximation algorithms provided that the set of precedence constraints has fractional dimension d. Our generalized approach yields the best known approximation ratios for all previously considered classes of precedence constraints, and it provides the first results for bounded degree and interval dimension 2 orders.As a negative result we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72792-7_11 | IPCO |
Keywords | Field | DocType |
special class,interval dimension,special case,approximation ratio,prominent open problem,precedence constraints,low fractional dimension,fractional dimension,single machine scheduling problem,approximation algorithm,precedence constraint,interval order | Discrete mathematics,Mathematical optimization,Single-machine scheduling,Computer science,Scheduling theory,Scheduling (computing),Bipartite graph,Regular polygon,Special case,Bounded function | Conference |
Volume | ISSN | Citations |
4513 | 0302-9743 | 8 |
PageRank | References | Authors |
0.53 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Ambühl | 1 | 357 | 18.50 |
| Monaldo Mastrolilli | 2 | 514 | 39.27 |
| Nikolaus Mutsanas | 3 | 35 | 3.00 |
| Ola Svensson | 4 | 349 | 36.31 |