nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.03.2018

Better approximability results for min–max tree/cycle/path cover problems

verfasst von: Wei Yu, Zhaohui Liu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the problem of covering the vertices of an undirected weighted graph with a given number of trees (cycles, paths) to minimize the weight of the maximum weight tree (cycle, path). Improved inapproximability lower bounds are proved and better approximation algorithms are designed for several variants of this problem.

Vorheriger Artikel Deadlock resolution in wait-for graphs by vertex/arc deletion

Nächster Artikel Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Arkin EM, Hassin R, Levin A (2006) Approximations for minimum and min–max vehicle routing problems. J Algorithms 59:1–18MathSciNetCrossRefMATH

Arora S, Grigni M, Karger DR, Klein P, Woloszyn A (1998) A polynomial-time approximation scheme for weighted planar graph TSP. In: The proceedings of the 9th annual ACM–SIAM symposium on discrete algorithms, pp 33–41

Bhattacharya B, Hu Y (2010) Approximation algorithms for the multi-vehicle scheduling problem. In: Cheong O, Chwa K-Y, Park K (eds) The proceedings of the 21th international symposium on algorithms and computation. Lecture notes in computer science, vol 6507. Springer, Heidelberg, pp 192–205

Campbell AM, Vandenbussche D, Hermann W (2008) Routing for relief efforts. Transp Sci 42:127–145CrossRef

Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh, PA

Dyer M, Frieze A (1986) Planar 3DM is NP-complete. J Algroithms 7:174–184CrossRefMATH

Even G, Garg N, Koemann J, Ravi R, Sinha A (2004) Min–max tree covers of graphs. Oper Res Lett 32:309–315MathSciNetCrossRefMATH

Farbstein B, Levin A (2015) Min–max cover of a graph with a small number of parts. Discrete Optim 16:51–61MathSciNetCrossRefMATH

Frederickson GN, Hecht MS, Kim CE (1978) Approximation algorithms for some routing problems. SIAM J Comput 7(2):178–193MathSciNetCrossRef

Garey M, Johnson D (1979) Computers and intractability. Freeman, San FranciscoMATH

Hopcroft J, Karp R (1973) An \(n^{2.5}\) algorithm for maximum matchings in bipartite graphs. SIAM J Comput 2:225–231MathSciNetCrossRefMATH

Jorati A (2013) Approximation algorithms for some min–max vehicle routing problems. Master Thesis, University of Alberta

Karakawa S, Morsy E, Nagamochi H (2011) Minmax tree cover in the Euclidean space. J Graph Algorithms Appl 15:345–371MathSciNetCrossRefMATH

Karuno Y, Nagamochi H (2003) 2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. Discrete Appl Math 129:433–447MathSciNetCrossRefMATH

Khani MR, Salavatipour MR (2014) Approximation algorithms for min–max tree cover and bounded tree cover problems. Algorithmica 69:443–460MathSciNetCrossRefMATH

Klein P (2008) A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J Comput 37:1926–1952MathSciNetCrossRefMATH

Nagamochi H (2005) Approximating the minmax rooted-subtree cover problem. IEICE Trans Fundam Electron E88–A:1335–1338CrossRef

Nagamochi H, Okada K (2003) Polynomial time 2-approximation algorithms for the minmax subtree cover problem. In: Ibaraki T, Katoh N, Ono H (eds) The proceedings of the 14th international symposium on algorithms and computation. Lecture notes in computer science, vol 2096. Springer, Heidelberg, pp 138–147

Nagarajan V, Ravi R (2012) Approximation algorithms for distance constrained vehicle routing problems. Networks 59(2):209–214MathSciNetCrossRefMATH

Sebo A, Vygen J (2014) Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34:597–629MathSciNetCrossRefMATH

Xu W, Liang W, Lin X (2015) Approximation algorithms for min–max cycle cover problems. IEEE Trans Comput 64:600–613MathSciNetCrossRefMATH

Xu Z, Wen Q (2010) Approximation hardness of min–max tree covers. Oper Res Lett 38:408–416MathSciNetCrossRefMATH

Xu Z, Xu L, Li C-L (2010) Approximation results for min–max path cover problems in vehicle routing. Naval Res Logist 57:728–748MathSciNetCrossRefMATH

Xu Z, Xu L, Zhu W (2012) Approximation results for a min–max location-routing problem. Discrete Appl Math 160:306–320MathSciNetCrossRefMATH

Yu W, Liu Z (2016) Improved approximation algorithms for some min–max and minimum cycle cover problems. Theor Comput Sci 654:45–58MathSciNetCrossRefMATH

Titel: Better approximability results for min–max tree/cycle/path cover problems
verfasst von: Wei Yu
Zhaohui Liu
Publikationsdatum: 01.03.2018
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0268-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2019

Preface to the special issue on computing and combinatorics

Agent incentives of a proportional sharing mechanism in resource sharing

Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

On the weighted safe set problem on paths and cycles

Deadlock resolution in wait-for graphs by vertex/arc deletion

Local search approximation algorithms for the k-means problem with penalties