Approximation algorithms for some vehicle routing problems

DOI10.1016/j.dam.2004.07.003zbMath1061.90006OpenAlexW2063605597MaRDI QIDQ1765372

Cristina Bazgan, Refael Hassin, Jérôme Monnot

Publication date: 23 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.07.003

zbMATH Keywords

TSPdifferential ratioVRP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items (10)

Differential approximation algorithm of FSMVRP ⋮ Approximation algorithms for distance constrained vehicle routing problems ⋮ A parameterized perspective on packing paths of length two ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ A survey on the structure of approximation classes ⋮ Packing paths: recycling saves time ⋮ A better differential approximation ratio for symmetric TSP ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ Approximation results for min-max path cover problems in vehicle routing ⋮ Approximation of the double traveling salesman problem with multiple stacks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Differential approximation results for the traveling salesman and related problems
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• Structure preserving reductions among convex optimization problems
• Maximizing the number of unused colors in the vertex coloring problem
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Better approximations for max TSP
• z-Approximations
• On the approximability of the traveling salesman problem (extended abstract)
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• Bounds and Heuristics for Capacitated Routing Problems
• On the Distance Constrained Vehicle Routing Problem
• P-Complete Approximation Problems
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• The Traveling Salesman Problem with Distances One and Two
• Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
• On the completeness of a generalized matching problem

This page was built for publication: Approximation algorithms for some vehicle routing problems