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

DOI10.1007/S10878-018-0268-8zbMATH Open1422.90048OpenAlexW2793244758WikidataQ130170375 ScholiaQ130170375MaRDI QIDQ2420656FDOQ2420656

Authors: Wei Yu, Zhaohui Liu 

Publication date: 6 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0268-8

Recommendations

• Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems
• Approximation hardness of min-max tree covers
• Improved approximation algorithms for the min-max tree cover and bounded tree cover problems
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Minimum-Weight Cycle Covers and Their Approximability

zbMATH Keywords

approximation algorithmtraveling salesman problempath covercycle coverapproximation hardnesstree cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Planar 3DM is NP-complete
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• 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
• Min-max tree covers of graphs.
• Approximation results for a min-max location-routing problem
• Approximation algorithms for distance constrained vehicle routing problems
• Min-max cover of a graph with a small number of parts
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for the multi-vehicle scheduling problem
• Approximation results for min-max path cover problems in vehicle routing
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Algorithms and Computation
• Approximations for minimum and min-max vehicle routing problems
• Minmax tree cover in the Euclidean space
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Approximation hardness of min-max tree covers
• Title not available (Why is that?)

Cited In (14)

• Approximation hardness of min-max tree covers
• An overview of graph covering and partitioning
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Vertex covering by paths on trees with its applications in machine translation
• A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
• Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems
• The heterogeneous rooted tree cover problem
• Approximation algorithms for some min-max postmen cover problems
• Improved approximations for tour and tree covers
• A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering
• Scheduling on a graph with release times
• Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints
• Better inapproximability bounds and approximation algorithms for MIN-MAX tree/cycle/path cover problems
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants

This page was built for publication: Better approximability results for min-max tree/cycle/path cover problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420656)