Abstract
An efficient combinatorial 2 approximation problem is developed to minimize weighted completion time on a single machine. The algorithm is based on solving minimum cuts, and hence is more efficient. Further, combined with a conversion algorithm, efficient combinatorial algorithms are obtained for several single and parallel machine variants in a unified way. A factor 2 integrality gap for the linear ordering relaxation is shown.
| Original language | English (US) |
|---|---|
| Pages | S873-S874 |
| State | Published - 1999 |
| Externally published | Yes |
| Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
| Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Baltimore, MD, USA |
| Period | 1/17/99 → 1/19/99 |
ASJC Scopus subject areas
- Software
- General Mathematics