✦ LIBER ✦
Approximate strong separation with application in fractional graph coloring and preemptive scheduling
✍ Scribed by Klaus Jansen
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 280 KB
- Volume
- 302
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we show that approximation algorithms for the weighted independent set and s-dimensional knapsack problem with ratio a can be turned into approximation algorithms with the same ratio for fractional weighted graph coloring and preemptive resource constrained scheduling. In order to obtain these results, we generalize known results by Gr otschel, Lovasz and Schrijver on separation, non-emptiness test, optimization and violation in the direction of approximability.