New LP relaxations for minimum cycle/path/tree cover problems

DOI10.1016/J.TCS.2019.05.041zbMATH Open1436.90147OpenAlexW2954210179WikidataQ127575553 ScholiaQ127575553MaRDI QIDQ2283007FDOQ2283007

Authors Wei Yu, Zhaohui Liu, Xiaoguang Bao

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.05.041

zbMATH Keywords

approximation algorithmintegrality gappath covervehicle routingcycle cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Recommendations

• New LP relaxations for minimum cycle/path/tree cover problems
• Improved approximation algorithms for some min-max and minimum cycle cover problems
• New approximation algorithms for the minimum cycle cover problem
• New approximation algorithms for the minimum cycle cover problem
• Improved approximation algorithms for min-max and minimum vehicle routing problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• 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
• Approximations for minimum and min-max vehicle routing problems
• 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
• Min-max tree covers of graphs.
• Minimum Vehicle Routing with a Common Deadline
• Minmax tree cover in the Euclidean space
• New approximation algorithms for the minimum cycle cover problem
• The vehicle routing problem
• The vehicle routing problem. Latest advances and new challenges.

Cited in

(3)

• An overview of graph covering and partitioning
• Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity
• New LP relaxations for minimum cycle/path/tree cover problems

Describes a project that uses

Uses Software

• VRP

This page was built for publication: New LP relaxations for minimum cycle/path/tree cover problems

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