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:
Efficient Algorithms for the Routing Open Shop with Unrelated Travel Times on Cacti Read chapter Read first chapter

2020 | OriginalPaper | Chapter

On PTAS for the Geometric Maximum Connected k-Factor Problem

Authors : Edward Gimadi, Ivan Rykov, Oxana Tsidulko

Published in: Optimization and Applications

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We consider the Connected k-factor problem (k-CFP): given a complete edge-weighted n-vertex graph, the goal is to find a connected k-regular spanning subgraph of maximum or minimum total weight. The problem is called geometric, if the vertices of a graph correspond to a set of points in a normed space \(\mathbb R^d\) and the weight of an edge is the distance between its endpoints. The k-CFP is a natural generalization of the well-known Traveling Salesman Problem, which is equivalent to the 2-CFP. In this paper we complement the known \((1-1/ k^2)\)-approximation algorithm for the maximum k-CFP from [Baburin et al., 2007] with an approximation algorithm for the geometric k-CFP, that guarantees a relative error \(\varepsilon = O\left( (k/n)^{1/(d+2)}\right) \). Together these two algorithms form an asymptotically optimal algorithm for the geometric k-CFP with an arbitrary value of k in an arbitrary normed space of fixed dimension d. Finally, the asymptotically optimal algorithm can be easily transformed into a PTAS for the considered geometric problem.

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 Comparison of Direct and Indirect Approaches for Numerical Solution of the Optimal Control Problem by Evolutionary Methods
next chapter Generalization of Controls Bimodality Property in the Optimal Exploitation Problem for Ecological Population with Binary Structure
Literature
1.
2.
Arkin, E.M., Chiang, Y., Mitchell, J.S.B., Skiena, S.S., Yang, T.: On the maximum scatter TSP. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 211–220 (1997)
3.
Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)MathSciNetCrossRef
4.
Bartal, Y., Gottlieb, L.-A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 663–672 (2012)
5.
Baburin, A.E., Gimadi, E.K.: Certain generalization of the maximum traveling salesman problem. J. Appl. Ind. Math. 1(4), 418–423 (2007)MathSciNetCrossRef
6.
Baburin, A.E., Gimadi, E.K.: An approximation algorithm for finding a d-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges. J. Appl. Ind. Math. 2(2), 155–166 (2008)MathSciNetCrossRef
7.
Baburin, A.E., Gimadi, E.K.: On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space. Proc. Steklov Inst. Math. 272(1), 1–13 (2011)MathSciNetCrossRef
8.
Barvinok, A., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G.J., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641–664 (2003)MathSciNetCrossRef
9.
Cheah, F., Corneil, D.G.: The complexity of regular subgraph recognition. Discret. Appl. Math. 27(1–2), 59–68 (1990)MathSciNetCrossRef
10.
11.
Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N.S., Rahul, C.S., Waanders, M.: Approximation algorithms for connected graph factors of minimum weight. J. Theory Comput. Syst. 62(2), 441–464 (2018)MathSciNetCrossRef
12.
Frieze, A., Pegden, W.: Separating subadditive Euclidean functionals. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2016, pp. 22–35 (2016)
13.
Fukunaga, T., Nagamochi, H.: Network design with edge-connectivity and degree constraints. Theory Comput. Syst. 45(3), 512–532 (2009)MathSciNetCrossRef
14.
Harary, F.: Graph Theory. Addison-Wesley Series in Mathematics. Addison-Wesley, Reading (1969)CrossRef
15.
Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: 15th Annual ACM Symposium on Theory of Computing, pp. 448–456. ACM, New York (1983)
16.
17.
Gimadi, E.Kh., Tsidulko, O.Yu.: Asymptotically optimal algorithm for the maximum m-peripatetic salesman problem in a normed space. In: Battiti, R., Brunato, M., Kotsireas, I., Pardalos, P.M. (eds.) LION 12 2018. LNCS, vol. 11353, pp. 402–410. Springer, Cham (2019). https://​doi.​org/​10.​1007/​978-3-030-05348-2_​33
18.
Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and its Variations. Kluwer Academic Publishers, Dortrecht (2002)MATH
19.
20.
21.
Serdyukov, A.I.: Asymptotically exact algorithm for the travelling salesman maximum problem in Euclidean space (In Russian). Upravlyaemye Sistemy 27, 79–87 (1987)MATH
22.
Shenmaier, V.V.: Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP. Discret. Appl. Math. 163(2), 214–219 (2014)MathSciNetCrossRef
23.
24.
Yazicioglu, A.Y., Egerstedt, M., Shamma, J.S.: Formation of robust multi-agent networks through self-organizing random regular graphs. IEEE Trans. Netw. Sci. Eng. 2(4), 139–151 (2015)MathSciNetCrossRef
Metadata
Title
On PTAS for the Geometric Maximum Connected k-Factor Problem
Authors
Edward Gimadi
Ivan Rykov
Oxana Tsidulko
Copyright Year
2020
Book
Optimization and Applications

Print ISBN: 978-3-030-38602-3

Electronic ISBN: 978-3-030-38603-0

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-38603-0_15

Premium Partner

    Image Credits