Improved approximation algorithms for min-max and minimum vehicle routing problems

DOI10.1007/978-3-319-21398-9_12MaRDI QIDQ3196380zbMATH OpenOpenAlexFDO

Authors Wei Yu, Zhaohui Liu

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_12

zbMATH Keywords

approximation algorithmcycle covertraveling salesman problemvehicle routing

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Improved approximation algorithms for some min-max and minimum cycle cover problems
• New approximation algorithms for the minimum cycle cover problem
• Constant-factor approximations for cycle cover problems
• New approximation algorithms for the minimum cycle cover problem
• Approximability of the minimum-weight \(k\)-size cycle cover problem

Cites work

• Algorithms and Computation
• Approximating the minmax rooted-tree cover in a tree
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• Approximation algorithms for the multi-vehicle scheduling problem
• Approximation results for a min-max location-routing problem
• Approximation results for min-max path cover problems in vehicle routing
• Approximations for minimum and min-max vehicle routing problems
• Capacitated dynamic lot-sizing problem with delivery/production time windows
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Min-max tree covers of graphs.
• Minmax tree cover in the Euclidean space
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Cited in

(16)

• Min-max cover of a graph with a small number of parts
• Approximation algorithms for some extensions of the maximum profit routing problem
• A fast \((2 + \frac{2}{7})\)-approximation algorithm for capacitated cycle covering
• New LP relaxations for minimum cycle/path/tree cover problems
• Min-Max vs. Min-Sum vehicle routing: a worst-case analysis
• Approximation results for min-max path cover problems in vehicle routing
• Improved Approximation Algorithms for Routing Shop Scheduling
• Constant-factor approximations for cycle cover problems
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• A fast (2 + 2/7)-approximation algorithm for capacitated cycle covering
• Approximations for minimum and min-max vehicle routing problems
• New approximation algorithms for the rooted budgeted cycle cover problem
• Improving the approximation ratio for capacitated vehicle routing
• New approximation algorithms for the rooted budgeted cycle cover problem
• New LP relaxations for minimum cycle/path/tree cover problems

This page was built for publication: Improved approximation algorithms for min-max and minimum vehicle routing problems

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