Better approximability results for min-max tree/cycle/path cover problems
From MaRDI portal
Publication:2420656
DOI10.1007/S10878-018-0268-8zbMath1422.90048OpenAlexW2793244758WikidataQ130170375 ScholiaQ130170375MaRDI QIDQ2420656
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
approximation algorithmtraveling salesman problempath covercycle coverapproximation hardnesstree cover
Related Items (8)
A Fast $$(2 + 2/7)$$-Approximation Algorithm for Capacitated Cycle Covering ⋮ An overview of graph covering and partitioning ⋮ Approximation and polynomial algorithms for the data mule scheduling with handling time and time span constraints ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ Approximation algorithms for the min-max mixed rural postmen cover problem and its variants ⋮ Scheduling on a graph with release times ⋮ Approximation algorithms for some min-max postmen cover problems ⋮ A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for some min-max and minimum cycle cover problems
- 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
- Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
- Min-max tree covers of graphs.
- Approximation results for a min-max location-routing problem
- Approximation hardness of min-max tree covers
- 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
- Min-max cover of a graph with a small number of parts
- Approximation algorithms for distance constrained vehicle routing problems
- 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
- A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
- Planar 3DM is NP-complete
- Algorithms and Computation
- Approximations for minimum and min-max vehicle routing problems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Minmax Tree Cover in the Euclidean Space
This page was built for publication: Better approximability results for min-max tree/cycle/path cover problems
