Approximate Pareto sets of minimal size for multi-objective optimization problems

被引：25

作者：

Bazgan, Cristina ^{[1
,2
]}

Jamain, Florian ^{[1
]}

Vanderpooten, Daniel ^{[1
]}

机构：

[1] Univ Paris 09, LAMSADE UMR 7243, PSL, F-75775 Paris 16, France

[2] Inst Univ France, Paris, France

来源：

OPERATIONS RESEARCH LETTERS | 2015年 / 43卷 / 01期

关键词：

Multi-objective optimization; Pareto set; Non-dominated points; Approximation algorithm; Greedy algorithm; SHORTEST PATHS;

D O I：

10.1016/j.orl.2014.10.003

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We are interested in a problem introduced by Vassilvitskii and Yannakakis (2005), the computation of a minimum set of solutions that approximates within an accuracy epsilon the Pareto set of a multi-objective optimization problem. We mainly establish a new 3-approximation algorithm for the bi-objective case. We also propose a study of the greedy algorithm performance for the tri-objective case when the points are given explicitly, answering an open question raised by Koltun and Papadimitriou in (2007). (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：1 / 6

页数：6

共 13 条

[1]

[Anonymous], MULTIPLE CRITERIA DE

[2] Solving efficiently the 0-1 multi-objective knapsack problem [J].

Bazgan, Cristina ;

Hugot, Hadrien ;

Vanderpooten, Daniel .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (01) :260-279

[3] Bicriterion single machine scheduling with resource dependent processing times [J].

Cheng, TCE ;

Janiak, A ;

Kovalyov, MY .

SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (02) :617-630

[4] SMALL APPROXIMATE PARETO SETS FOR BIOBJECTIVE SHORTEST PATHS AND OTHER PROBLEMS [J].

Diakonikolas, Ilias ;

Yannakakis, Mihalis .

SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1340-1371

[5]

Ehrgott M., 2000, MULTICRITERIA OPTIMI

[6] Approximating multiobjective knapsack problems [J].

Erlebach, T ;

Kellerer, H ;

Pferschy, U .

MANAGEMENT SCIENCE, 2002, 48 (12) :1603-1612

[7] New approaches to multi-objective optimization [J].

Grandoni, Fabrizio ;

Ravi, R. ;

Singh, Mohit ;

Zenklusen, Rico .

MATHEMATICAL PROGRAMMING, 2014, 146 (1-2) :525-554

[8] A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem [J].

Hong, SP ;

Chung, SJ ;

Park, BH .

OPERATIONS RESEARCH LETTERS, 2004, 32 (03) :233-239

[9] Approximately dominating representatives [J].

Koltun, Vladlen ;

Papadimitriou, Christos H. .

THEORETICAL COMPUTER SCIENCE, 2007, 371 (03) :148-154

[10]

Papadimitriou CH, 2000, ANN IEEE SYMP FOUND, P86

← 1 2 →