  


Pareto Optima of Multicriteria Integer Linear Programs
Jesús A. De Loera(deloeramath.ucdavis.edu) Abstract: We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomialtime algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomialspace polynomialdelay prescribedorder enumeration algorithm for arbitrary projections of the Pareto set; 3. an algorithm to minimize the distance of a Pareto optimum from a prescribed comparison point with respect to arbitrary polyhedral norms; 4. a fully polynomialtime approximation scheme for the problem of minimizing the distance of a Pareto optimum from a prescribed comparison point with respect to the Euclidean norm. Keywords: multiobjective optimization; integer programming; complexity in fixed dimension Category 1: Integer Programming (Other ) Category 2: Other Topics (MultiCriteria Optimization ) Citation: Download: [PDF] Entry Submitted: 07/10/2007 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  