Approximate strong separation with appli
โ
Klaus Jansen
๐
Article
๐
2003
๐
Elsevier Science
๐
English
โ 280 KB
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 obta