Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems
作者： Ilias Diakonikolas , Mihalis Yannakakis
DOI: 10.1137/080724514
关键词: Multi-objective optimization 、 Mathematical optimization 、 Spanning tree 、 Combinatorics 、 Mathematics 、 Upper and lower bounds 、 Time complexity 、 Pareto distribution 、 Matching (graph theory) 、 Pareto principle 、 Shortest path problem
摘要: We investigate the problem of computing a minimum set solutions that approximates within specified accuracy $\epsilon$ Pareto curve multiobjective optimization problem. show for broad class biobjective problems (containing many important widely studied such as shortest paths, spanning tree, matching, and others), we can compute in polynomial time an $\epsilon$-Pareto contains at most twice set. Furthermore factor 2 is tight these problems; i.e., it NP-hard to do better. present upper lower bounds three or more objectives, well dual number $k$ which provide good approximation curve.
harvard.edu
springer.com
ed.ac.uk
aip.org
iliasdiakonikolas.org 参考文章(44)
Pierre Hansen, Bicriterion Path Problems Springer, Berlin, Heidelberg. pp. 109- 127 ,(1980) , 10.1007/978-3-642-48782-8_9
JosÉ Figueira, Salvatore Greco, Matthias Ehrogott, Multiple criteria decision analysis: state of the art surveys Operations Research and Management Science. ,(2005) , 10.1007/B100605
Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten, Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack Algorithms – ESA 2005. pp. 862- 873 ,(2005) , 10.1007/11561071_76
Aaron Archer, Two O (log* k)-Approximation Algorithms for the Asymmetric k-Center Problem integer programming and combinatorial optimization. pp. 1- 14 ,(2001) , 10.1007/3-540-45535-3_1
R. Ravi, M. X. Goemans, The Constrained Minimum Spanning Tree Problem scandinavian workshop on algorithm theory. pp. 66- 75 ,(1996) , 10.1007/3-540-61422-2_121
Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten, Complexity of the Min-Max (Regret) Versions of Cut Problems Algorithms and Computation. pp. 789- 798 ,(2005) , 10.1007/11602613_79
Eric Angel, Evripidis Bampis, Alexander Kononov, None, A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs european symposium on algorithms. pp. 194- 205 ,(2001) , 10.1007/3-540-44676-1_16
C.H. Papadimitriou, M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources foundations of computer science. pp. 86- 92 ,(2000) , 10.1109/SFCS.2000.892068
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph (Seffi) Naor, Asymmetric k-center is log*n-hard to approximate Journal of the ACM. ,vol. 52, pp. 538- 551 ,(2005) , 10.1145/1082036.1082038
Sundar Vishwanathan, An O(log*n) approximation algorithm for the asymmetric p-center problem symposium on discrete algorithms. ,vol. 27, pp. 1- 5 ,(1996) , 10.5555/313852.313861