Optimization Online


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

Shashi Mittal(mshashi***at***alum.mit.edu)
Andreas S. schulz(schulz***at***mit.edu)

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 multi-objective 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 front of the functions which 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 and for 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.

Keywords: Combinatorial optimization, approximation schemes, scheduling, assortment optimization

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Robust Optimization

Citation: Technical Report, Operations Research Center, Massachusetts Institute of Technology

Download: [Postscript][PDF]

Entry Submitted: 09/07/2011
Entry Accepted: 09/07/2011
Entry Last Modified: 09/07/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society