Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Travelling on Graphs with Small Highway Dimension

Authors : Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] as a model for transportation networks, on which TSP and STP naturally occur for various applications in logistics. It was previously shown [Feldmann et al. ICALP 2015] that these problems admit a quasi-polynomial time approximation scheme (QPTAS) on graphs of constant highway dimension. We demonstrate that a significant improvement is possible in the special case when the highway dimension is 1, for which we present a fully-polynomial time approximation scheme (FPTAS). We also prove that STP is weakly \(\mathsf {NP}\)-hard for these restricted graphs. For TSP we show \(\mathsf {NP}\)-hardness for graphs of highway dimension 6, which answers an open problem posed in [Feldmann et al. ICALP 2015].

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Shortest Reconfiguration of Matchings
next chapter The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
Footnotes
1
A metric is said to have doubling dimension d if for all \(r>0\) every ball of radius r can be covered by at most \(2^d\) balls of half the radius r/2.
 
2
It is often assumed that all shortest paths are unique when defining the highway dimension, since this allows good polynomial approximations of this graph parameter [2]. In this work however, we do not rely on these approximations, and thus do not require uniqueness of shortest paths.
 
3
The proofs of Theorems 3 and 4 are deferred to the full version of the paper.
 
4
See [24, Section 9] and [15] for detailed discussions on different definitions of the highway dimension.
 
Literature
1.
Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. J. ACM 63(5), 41 (2016)MathSciNetCrossRef
2.
3.
Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the 21st Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 782–793 (2010)
4.
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)MathSciNetCrossRef
5.
Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of the 9th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 33–41 (1998)
6.
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: Proceedings of the 33rd Annual IEEE Symposium Foundations Computer Science (FOCS), pp. 14–23 (1992)
7.
Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean \(k\)-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium Theory Computer (STOC), pp. 106–113 (1998)
8.
Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of the 44th Annual ACM Symposium Theory Computer (STOC), pp. 663–672 (2012)
9.
Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74, pp. 175–192 (2009)
10.
Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Proceedings of the 9th Workshop Algorithm Engineering and Experiments (ALENEX) (2007)CrossRef
11.
Bateni, M., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58, 21:1–21:37 (2011)MathSciNetCrossRef
12.
Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for \(k\)-center, \(k\)-median, and capacitated vehicle routing in bounded highway dimension. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pp. 8:1–8:15 (2018)
13.
Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inform. Process. Lett. 32, 171–176 (1989)MathSciNetCrossRef
14.
Bland, R., Shallcross, D.: Large traveling salesman problems arising from experiments in X-ray crystallography: a preliminary report on computation. Oper. Res. Lett. 8, 125–128 (1989)MathSciNetCrossRef
15.
16.
Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 196–207. Springer, Heidelberg (2013). https://​doi.​org/​10.​1007/​978-3-642-39206-1_​17CrossRef
17.
18.
Borradaile, G., Kenyon-Mathieu, C., Klein, P.: A polynomial-time approximation scheme for Steiner tree in planar graphs. In: Proceedings of the 18th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1285–1294 (2007)
19.
Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: An improved LP-based approximation for Steiner tree. In: Proceedings of the 42nd Annual ACM Symposium Theory Computer (STOC), pp. 583–592 (2010)
20.
Chen, C.Y., Grauman, K.: Efficient activity detection in untrimmed video with max-subgraph search. IEEE Trans. Pattern Anal. Mach. Intell. 39, 908–921 (2018)CrossRef
21.
Chlebík, M., Chlebíková, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406, 207–214 (2008)MathSciNetCrossRef
22.
Chowdhury, S.A., Shackney, S.E., Heselmeyer-Haddad, K., Ried, T., Schäffer, A.A., Schwartz, R.: Phylogenetic analysis of multiprobe uorescence in situ hybridization data from tumor cell populations. Bioinformatics 29, i189–i198 (2013)CrossRef
23.
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388. Graduate School of Industrial Administration, Carnegie Mellon University (1976)
24.
Feldmann, A.E., Fung, W.S., Könemann, J., Post, I.: A (1+\(\epsilon \))-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 41, 1667–1704 (2018)MathSciNetCrossRef
25.
Feldmann, A.E.: Fixed parameter approximations for \(k\)-center problems in low highway dimension graphs. Algorithmica (2018)
26.
Feldmann, A.E., Marx, D.: The parameterized hardness of the k-center problem in transportation networks. In: Proceedings of the 16th Scandinavian Symposium and Workshop Algorithm Theory (SWAT), pp. 19:1–19:13 (2018)
27.
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)MathSciNetCrossRef
28.
Grigni, M., Koutsoupias, E., Papadimitriou, C.H.: An approximation scheme for planar graph TSP. In: Proceedings of the 36th Annual IEEE Symposium Foundations Computer Science (FOCS), pp. 640–645 (1995)
29.
Grötschel, M., Holland, O.: Solution of large-scale symmetric travelling salesman problems. Math. Program. 51, 141–202 (1991)MathSciNetCrossRef
30.
Held, S., Korte, B., Rautenbach, D., Vygen, J.: Combinatorial optimization in VLSI design. In: Chvatal, V. (ed.) Combinatorial Optimization: Methods and Applications, pp. 33–96. IOS Press, Amsterdam (2011)MATH
31.
Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3), 533–550 (1986)MathSciNetCrossRef
32.
Hougardy, S., Prömel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: Proceedings of the 10th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 448–453 (1999)
33.
34.
Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81, 1665–1677 (2015)MathSciNetCrossRef
35.
Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for (\(k, r\))-center. In: Proceedings of the 28th International Symposium Algorithms Computer (ISAAC), pp. 50:1–50:13 (2017)
36.
Klein, P.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926–1952 (2008)MathSciNetCrossRef
37.
Kosowski, A., Viennot, L.: Beyond highway dimension: small distance labels using tree skeletons. In: Proceedings of the 28th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 1462–1478 (2017)
38.
Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: Proceedings of the 47th Annual IEEE Symposium Foundations Computer Science (FOCS), pp. 119–132 (2006)
39.
40.
Laporte, G., Nobert, Y., Desrochers, M.: Optimal routing under capacity and distance restrictions. Oper. Res. 33, 1050–1073 (1985)MathSciNetCrossRef
41.
Lenstra, J., Rinnooy Kan, A.: Some simple applications of the traveling salesman problem. Oper. Res. Quart. 26, 717–733 (1975)CrossRef
42.
Ljubić, I., Weiskirchner, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prizecollecting Steiner tree problem. Math. Program. 105, 427–449 (2006)MathSciNetCrossRef
43.
44.
Mitchell, J.S.B.: 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)MathSciNetCrossRef
45.
Papadimitriou, C.H., Vempala, S.: On the approximability of the traveling salesman problem. Combinatorica 26, 101–120 (2006)MathSciNetCrossRef
46.
Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discret. Math. 19, 122–134 (2005)MathSciNetCrossRef
47.
Sebő, A., Vygen, J.: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34, 1–34 (2014)MathSciNetCrossRef
48.
Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and Steiner tree. SIAM J. Comput. 30, 475–485 (2000)MathSciNetCrossRef
49.
Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)MATH
Metadata
Title
Travelling on Graphs with Small Highway Dimension
Authors
Yann Disser
Andreas Emil Feldmann
Max Klimm
Jochen Könemann
Copyright Year
2019
Book
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-30786-8_14

Premium Partner

    Image Credits