Metric TSP
- PDF / 213,637 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 58 Downloads / 177 Views
Recommended Reading 1. Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog()competitive algorithm for metrical task systems. In: Proceedings of the 29th annual ACM Symposium on the Theory of Computing, pp. 711–719. ACM, New York (1997) 2. Bartal, Y., Bollobás, B., Mendel, M.: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci. 72, 890–921 (2006) 3. Bartal, Y., Mendel, M.: Multiembedding of metric spaces. SIAM J. Comput. 34, 248–259 (2004) 4. Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, Cambridge, UK (1998) 5. Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM 39, 745–763 (1992) 6. Burley, W.R., Irani, S.: On algorithm design for metrical task systems. Algorithmica 18, 461–485 (1997) 7. Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem and the work function algorithm. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. The State of the Art. LNCS, vol. 1442, ch. 4, pp. 74–96. Springer, London (1998) 8. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69, 485–497 (2004) 9. Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. SIAM J. Comput. 32, 1403–1422 (2003) 10. Irani, S., Seiden, S.S.: Randomized algorithms for metrical task systems. Theor. Comput. Sci. 194, 163–182 (1998) 11. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11, 208–230 (1990) 12. Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc. 9(2), 253–275 (2007)
Metric TSP 1976; Christofides MARKUS BLÄSER Department of Computer Science, Saarland University, Saarbrücken, Germany Keywords and Synonyms Metric traveling salesman problem; Metric traveling salesperson problem Problem Definition The Traveling Salesman Problem (TSP) is the following optimization problem: Input: A complete loopless undirected graph G = (V ; E; w) with a weight function w : E ! Q0 that assigns to each edge a non-negative weight. Feasible solutions: All Hamiltonian tours, i. e, the subgraphs H of G that are connected, and each node in them that has degree two.
M
Objective function: The weight function w(H) = w(e) of the tour. Goal: Minimization.
P
e2H
The TSP is an NP-hard optimization problem. This means that a polynomial time algorithm for the TSP does not exist unless P = NP. One way out of this dilemma is provided by approximation algorithms. A polynomial time algorithm for the TSP is called an ˛-approximation algorithm if the tour H produced by the algorithm fulfills w(H) ˛ OPT(G). Here OPT(G) is the weight of a minimum weight tour of G. If G is clear from the context, one just writes OPT. An ˛-approximation algorithm always produces a feasible solution whose objective value is at most a factor of ˛ away from the optimum value. ˛ is also called the approximation factor or performance guara
Data Loading...
