Approximation algorithms for solving the constrained arc routing problem in mixed graphs

DOI10.1016/j.ejor.2014.04.039zbMath1339.90279OpenAlexW2008216759MaRDI QIDQ297063

Honglin Ding, Ko-Wei Lih, Jianping Li

Publication date: 24 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.04.039

zbMATH Keywords

combinatorial optimizationapproximation algorithmcombinatorial algorithmarc routinglower/upper demand bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (1)

Approximation Algorithms for a Mixed Postman Problem with Restrictions on the Arcs

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search for the undirected capacitated arc routing problem with profits
• A general vehicle routing problem
• The vehicle routing problem. Latest advances and new challenges.
• A strongly polynomial minimum cost circulation algorithm
• Eulerian graphs and related topics. Part 1, Volume 2
• On the mixed Chinese postman problem
• A GRASP heuristic for the mixed Chinese postman problem
• A guided local search heuristic for the capacitated arc routing problem
• Heuristic method for a mixed capacitated arc routing problem: A refuse collection application
• An efficient transformation of the generalized vehicle routing problem
• Multi-objective vehicle routing problems
• A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
• The Vehicle Routing Problem
• A threshold of ln n for approximating set cover
• On a routing problem
• Finding minimum-cost circulations by canceling negative cycles
• Capacitated arc routing problems
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the complexity of edge traversing
• Approximation Algorithms for Some Postman Problems
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Matching, Euler tours and the Chinese postman
• An optimal algorithm for the mixed Chinese postman problem
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Approximation algorithms for solving the constrained arc routing problem in mixed graphs