Approximation schemes for a class of subset selection problems

Kirk Pruhs, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
80 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationLATIN 2004: Theoretical Informatics
Subtitle of host publication6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004. Proceedings
EditorsMartin Farach-Colton
Place of PublicationHeidelberg
PublisherSpringer
Pages203-211
Number of pages8
ISBN (Electronic)978-3-540-24698-5
ISBN (Print)978-3-540-21258-4
DOIs
Publication statusPublished - 2004
Event6th Latin American Symposium on Theoretical Informatics, LATIN 2004 - Buenos Aires, Argentina
Duration: 5 Apr 20048 Apr 2004
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2976
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th Latin American Symposium on Theoretical Informatics, LATIN 2004
Abbreviated titleLATIN
CountryArgentina
CityBuenos Aires
Period5/04/048/04/04

Keywords

  • METIS-219783
  • Schedule Problem
  • Approximation Scheme
  • Single Machine
  • Knapsack Problem
  • Combinatorial Optimization Problem

Fingerprint Dive into the research topics of 'Approximation schemes for a class of subset selection problems'. Together they form a unique fingerprint.

Cite this