Approximation schemes for a class of subset selection problems

@article{citeulike:2949045, abstract = {In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time.}, author = {Pruhs, Kirk and Woeginger, Gerhard J. }, booktitle = {Latin American Theoretical Informatics}, citeulike-article-id = {2949045}, doi = {10.1016/j.tcs.2007.03.006}, journal = {Theoretical Computer Science}, keywords = {algorithms, combinatorics, optimization}, month = {August}, number = {2}, pages = {151--156}, posted-at = {2008-07-01 19:38:55}, priority = {2}, title = {Approximation schemes for a class of subset selection problems}, url = {http://dx.doi.org/10.1016/j.tcs.2007.03.006}, volume = {382}, year = {2007} }

TY - JOUR ID - citeulike:2949045 L3 - citeulike-article-id:2949045 TI - Approximation schemes for a class of subset selection problems T2 - Latin American Theoretical Informatics JF - Theoretical Computer Science VL - 382 IS - 2 SP - 151 EP - 156 N2 - In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time. KW - algorithms KW - combinatorics KW - optimization AU - Pruhs, Kirk AU - Woeginger, Gerhard PY - 2007/08/31/ UR - http://dx.doi.org/10.1016/j.tcs.2007.03.006 ER -