  


A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One
Shashi Mittal(mshashialum.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 multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Paretooptimal front of the functions which constitute the given objective. Using this idea, we give the first fully polynomial time approximation schemes for the maxmin 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  