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

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

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)

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The vehicle routing problem
• The vehicle routing problem. Latest advances and new challenges.
• Min-max tree covers of graphs.
• Approximation results for a min-max location-routing problem
• Approximation algorithms for distance constrained vehicle routing problems
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation algorithms for the multi-vehicle scheduling problem
• 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
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• 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.
• New approximation algorithms for the minimum cycle cover problem
• Minimum Vehicle Routing with a Common Deadline

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

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)