A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one

Shashi Mittal, Andreas S. Schulz

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

9 Scopus citations

Abstract

In this paper, we propose a general framework for designing fully polynomial time approximation schemes for combinatorial optimization problems, in which more than one objective function are combined into one using any norm. The main idea is to exploit the approximate Pareto-optimal frontier for multi-criteria optimization problems. Using this approach, we obtain an FPTAS for a novel resource allocation problem, for the problem of scheduling jobs on unrelated parallel machines, and for the Santa Claus problem, when the number of agents/machines is fixed, for any norm, including the l - norm. Moreover, either FPTAS can be implemented in a manner so that the space requirements are polynomial in all input parameters. We also give approximation algorithms and hardness results for the resource allocation problem when the number of agents is not fixed.

Original languageEnglish
Title of host publicationApproximation, Randomization and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
Pages179-192
Number of pages14
DOIs
StatePublished - 2008
Externally publishedYes
Event11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 - Boston, MA, United States
Duration: 25 Aug 200827 Aug 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5171 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
Country/TerritoryUnited States
CityBoston, MA
Period25/08/0827/08/08

Fingerprint

Dive into the research topics of 'A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one'. Together they form a unique fingerprint.

Cite this