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:
Global and Local Search Methods for D.C. Constrained Problems Read chapter Read first chapter

2020 | OriginalPaper | Chapter

On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

Authors : Edward Kh. Gimadi, Ivan A. Rykov

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We consider the intractable problem of finding m edge-disjoint vertex covers in d-dimensional normed space with maximum total weight, such that each of them has exactly k cycles. We construct a polynomial-time approximation algorithm for solving this problem and derive conditions of its asymptotical optimality.

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 Using Integer Programming to Search for Counterexamples: A Case Study
next chapter D.C. Constrained Optimization Approach for Solving Metal Recovery Processing Problem
Literature
1.
Arora, S.: Polynomial-programming: methods and applications. In: Reeves, C.R. (ed.) NATO Advanced Study Institutes Series, Series C: Mathematical and Physical Sciences, vol. 19, pp. 1730–178. Reidel, Dordrecht (1975)
2.
Baburin, A.E., Gimadi, E.Kh.: On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space. Proc. Steklov Inst. Math. 272(Suppl. 1), 1–13 (2011)
3.
Barvinok, A.I., Gimadi, E.Kh., Serdyukov, A.I.: The maximum TSP. In: Punnen, A., Gutin, G. (eds.) The Traveling Salesman Problem and Its Variations, pp. 585–608. Kluwer Acad. Publ., Dordrecht (2002)
4.
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441. Academic Press, New York (1976)
5.
De Kort, J.B.J.M.: Upper bounds and lower bounds for the symmetric K peripatetic salesman problem. Optimization 23(4), 357–367 (1992)MathSciNetCrossRef
6.
Duhenne, E., Laporte, G., Semet, F.: The undirected m-capacitated peripatetic salesman problem. Eur. J. Oper. Res. 223(3), 637–643 (2012) MathSciNetCrossRef
7.
Gimadi, E.Kh.: A new version of the asymptotically optimal algorithm for solving the Euclidean maximum traveling salesman problem. In: Proceedings of the 12th Baykal International Conference 2001, Irkutsk, vol. 1, pp. 117–123 (2001). (in Russian)
8.
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
9.
Khachay, M., Neznakhina, E.: Approximation of Euclidean k-size cycle cover problem. Croatian Oper. Res. Rev. (CRORR) 5, 177–188 (2014)MathSciNetCrossRef
10.
Khachay, M., Neznakhina, E.: Polynomial-time approximations scheme for a Euclidean problem on a cycle covering of agraph. Tr. Inst. Matematiki i mehaniki UrORAN 20(4), 297–311 (2014). (in Russian)
11.
Gimadi, E.Kh.: A new version of the asymptotically optimal algorithm for solving the Euclidean maximum traveling salesman problem. In: Proceedings of the 12th Baykal International Conference, Irkutsk, vol. 1, pp. 117–123 (2001). (in Russian)
12.
Gimadi, E.Kh., Rykov, I.A.: Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles. Proc. Steklov Inst. Math. 295, 57–67 (2016)
13.
14.
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)MATH
15.
16.
Papadimitriou, C.: Euclidean TSP is NP-complete. Theor. Comput. Sci. 4, 237–244 (1977)CrossRef
17.
18.
Shenmaier, V.V.: An algorithm for the polyhedral cyclic covering problem with restrictions on the number and length of cycles. Tr. IMM UrORAN 24(3), 272–280 (2018)MathSciNetCrossRef
19.
Shenmaier, V.V.: Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP. Discrete Appl. Math. 163(2), 214–219 (2014)MathSciNetCrossRef
20.
Barvinok, A.I., Fekete, S.P., Johnson, D.S., Tamir, A., Woeginger, G., Woodroofe, R.: The geometric maximum traveling salesman problem. J. ACM 50(5), 641–664 (2003)MathSciNetCrossRef
21.
Serdyukov, A.I.: An asymptotically optimal algorithm for the maximum traveling salesman problem in Euclidean space. Upravlyaemye sistemy, Novosibirsk 27, 79–87 (1987). (in Russian)
Metadata
Title
On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space
Authors
Edward Kh. Gimadi
Ivan A. Rykov
Copyright Year
2020
Book
Mathematical Optimization Theory and Operations Research

Print ISBN: 978-3-030-49987-7

Electronic ISBN: 978-3-030-49988-4

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-49988-4_6

Premium Partner

    Image Credits