Document Open Access Logo

Effectiveness of Local Search for Geometric Optimization

Authors Vincent Cohen-Addad, Claire Mathieu

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.329.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Vincent Cohen-Addad
Claire Mathieu

Cite AsGet BibTex

Vincent Cohen-Addad and Claire Mathieu. Effectiveness of Local Search for Geometric Optimization. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 329-344, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.329

Abstract

What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude 1/epsilon^c is an approximation scheme for the following problems in the Euclidean plane: TSP with random inputs, Steiner tree with random inputs, uniform facility location (with worst case inputs), and bicriteria k-median (also with worst case inputs). The randomness assumption is necessary for TSP.
Keywords
  • Local Search
  • PTAS
  • Facility Location
  • k-Median
  • TSP
  • Steiner Tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Arora. Polynomial time approximation schemes for euclidean TSP and other geometric problems. In Symp. on Foundations of Computer Science, FOCS'96, Burlington, Vermont, USA, 14-16 October, 1996, pages 2-11, 1996. Google Scholar
  2. S. Arora. Nearly linear time approximation schemes for euclidean TSP and other geometric problems. In Symp. on Foundations of Computer Science, FOCS'97, Miami Beach, Florida, USA, October 19-22, 1997, pages 554-563, 1997. Google Scholar
  3. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004. Google Scholar
  4. J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. Mathematical Proc. of the Cambridge Philosophical Society, 55:299-327, 1959. Google Scholar
  5. T. M. Chan and S. Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. In Proc. of the Symp. on Computational Geometry, SCG'09, pages 333-340. ACM, 2009. Google Scholar
  6. B. Chandra, H. J. Karloff, and C. A. Tovey. New results on the old k-opt algorithm for the TSP. In Proc. of the ACM-SIAM Symp. on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia., pages 150-159, 1994. Google Scholar
  7. M. Charikar and S. Guha. Improved combinatorial algorithms for facility location problems. SIAM J. Comput., 34(4):803-824, 2005. Google Scholar
  8. F. A. Chudak and D. P. Williamson. Improved approximation algorithms for capacitated facility location problems. Math. Program., 102(2):207-222, March 2005. Google Scholar
  9. G. A. Croes. A method for solving traveling salesman problems. Operations Research, 6(6):791-812, 1958. Google Scholar
  10. M. Gibson and I. A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the logn barrier - (extended abstract). In Algorithms - ESA 2010, European Symp., Liverpool, UK, September 6-8, 2010. Proc., Part I, pages 243-254, 2010. Google Scholar
  11. D. S Johnson and L. A McGeoch. The traveling salesman problem : A case study in local optimization. Local Search in Combinatorial Optimization, 1:215-310, 1997. Google Scholar
  12. T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89-112, 2004. Google Scholar
  13. R. M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of Operations Research, 2(3):209-224, 1977. Google Scholar
  14. S. G. Kolliopoulos and S. Rao. A nearly linear-time approximation scheme for the euclidean k-median problem. SIAM J. Comput., 37(3):757-782, 2007. Google Scholar
  15. M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. J. Algorithms, 37(1):146-188, 2000. Google Scholar
  16. E. Krohn, M. Gibson, G. Kanade, and K. R. Varadarajan. Guarding terrains via local search. JoCG, 5(1):168-178, 2014. Google Scholar
  17. S. Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, The, 44(10):2245-2269, 1965. Google Scholar
  18. S. Lin and B. W Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498-516, 1973. Google Scholar
  19. N. Megiddo and K. J. Supowit. On the complexity of some common geometric location problems. SIAM J. Comput., 13(1):182-196, 1984. Google Scholar
  20. O. Mersmann, B. Bischl, J. Bossek, H. Trautmann, M. Wagner, and F. Neumann. Local search and the traveling salesman problem: A feature-based characterization of problem hardness. In Learning and Intelligent Optimization - 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers, pages 115-129, 2012. Google Scholar
  21. J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999. Google Scholar
  22. N. H. Mustafa and S. Ray. PTAS for geometric hitting set problems via local search. In Proc. of the ACM Symp. on Computational Geometry, Aarhus, Denmark, pages 17-22, 2009. Google Scholar
  23. S. Rao and W. D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In Proc. of the ACM Symp. on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 540-550, 1998. Google Scholar
  24. G. Robins and A. Zelikovsky. Improved steiner tree approximation in graphs. In Proc. of the ACM-SIAM Symp. on Discrete Algorithms, SODA, pages 770-779. SIAM, 2000. Google Scholar
  25. D. J. Rosenkrantz, R. Edwin Stearns, and P. M. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput., 6(3):563-581, 1977. Google Scholar
  26. J. Vygen. Approximation algorithms for facility location problems. Technical Report 05950, Research Institute for Discrete Mathematics, University of Bonn, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact