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

DOI10.1016/J.EJOR.2014.04.039zbMATH Open1339.90279OpenAlexW2008216759MaRDI QIDQ297063FDOQ297063

Authors: Honglin Ding, Jianping Li, Ko-Wei Lih 

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

Recommendations

• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• scientific article; zbMATH DE number 1187150
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• The mixed general routing polyhedron

zbMATH Keywords

combinatorial optimizationapproximation algorithmcombinatorial algorithmarc routinglower/upper demand bound

Mathematics Subject Classification ID

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

Cites Work

• A threshold of ln n for approximating set cover
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Title not available (Why is that?)
• On a routing problem
• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Matching, Euler tours and the Chinese postman
• The vehicle routing problem
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• 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
• Title not available (Why is that?)
• Finding minimum-cost circulations by canceling negative cycles
• Title not available (Why is that?)
• Capacitated arc routing problems
• On the complexity of edge traversing
• Approximation Algorithms for Some Postman Problems
• Title not available (Why is that?)
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• An optimal algorithm for the mixed Chinese postman problem
• Local search for the undirected capacitated arc routing problem with profits
• Title not available (Why is that?)
• A general vehicle routing problem

Cited In (9)

• A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
• Title not available (Why is that?)
• An updated annotated bibliography on arc routing problems
• Title not available (Why is that?)
• A comparison of two different formulations for arc routing problems on mixed graphs
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• Approximation algorithm for min-max cycle cover problem on a mixed graph
• Approximation algorithms for two clustered arc routing problems
• Approximation algorithms for a mixed postman problem with restrictions on the arcs

Uses Software

• Algorithm 97

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

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