Approximation schemes for NP-hard geometric optimization problems: a survey

被引:69
作者
Arora, S [1 ]
机构
[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA
关键词
D O I
10.1007/s10107-003-0438-y
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Traveling Salesman, Steiner Tree, and many other famous geometric optimization problems are NP-hard. Since we do not expect to design efficient algorithms that solve these problems optimally, researchers have tried to design approximation algorithms, which can compute a provably near-optimal solution in polynomial time. We survey such algorithms, in particular a new technique developed over the past few years that allows us to design approximation schemes for many of these problems. For any fixed constant c> 0, the algorithm can compute a solution whose cost is at most (1 + c) times the optimum. (The running time is polynomial for every fixed c> 0, and in many cases is even nearly linear.) We describe how these schemes are designed, and survey the status of a large number of problems.
引用
收藏
页码:43 / 69
页数:27
相关论文
共 93 条
[1]   THE COMPLEXITY OF THE TRAVELING REPAIRMAN PROBLEM [J].
AFRATI, F ;
COSMADAKIS, S ;
PAPADIMITRIOU, CH ;
PAPAGEORGIOU, G ;
PAPAKOSTANTINOU, N .
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1986, 20 (01) :79-87
[2]  
AFRATI F, 1999, P 40 ANN IEEE S FDN, P32
[3]  
ALTHOFER I, 1993, DISCRETE COMPUTATION
[4]  
[Anonymous], 2001, TION ENGRG
[5]  
[Anonymous], 1996, CS9606 U VIRG
[6]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[7]  
[Anonymous], P CAMB PHILO SOC, DOI DOI 10.1017/S0305004100034095
[8]  
Applegate D., 1998, DOC MATH J DTSCH MAT, P645
[9]   Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].
Arora, S .
JOURNAL OF THE ACM, 1998, 45 (05) :753-782
[10]  
Arora S., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P106, DOI 10.1145/276698.276718