A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

Shashi Mittal () and Andreas S. Schulz ()
Additional contact information
Shashi Mittal: Amazon.com, Seattle, Washington 98109
Andreas S. Schulz: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2013, vol. 61, issue 2, 386-397

Abstract: In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model.

Keywords: analysis of algorithms; combinatorial optimization; networks/graphs; production/scheduling (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1093 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:386-397

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().