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

Honglin Ding, Jianping Li and Ko-Wei Lih

European Journal of Operational Research, 2014, vol. 239, issue 1, 80-88

Abstract: Given a mixed graph G with vertex set V, let E and A denote the sets of edges and arcs, respectively. We use Q+ and Z+ to denote the sets of positive rational numbers and positive integers, respectively. For any connected mixed graph G=(V,E∪A;w;l,u) with a length function w:E∪A→Q+ and two integer functions l,u:E∪A→Z+ satisfying l(e)⩽u(e) for each e∈E∪A, we are asked to determine a minimum length tour T traversing each e∈E∪A at least l(e) and at most u(e) times. This new constrained arc routing problem generalizes the mixed Chinese postman problem. Let n=|V| and m=|E∪A| denote the number of vertices and edges (including arcs), respectively. Using network flow techniques, we design a (1+1/l0)-approximation algorithm in time O(n2m3logn) to solve this constrained arc routing problem such that l(e)Keywords: Combinatorial optimization; Arc routing; Lower/upper demand bound; Approximation algorithm; Combinatorial algorithm (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714003816
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:239:y:2014:i:1:p:80-88

DOI: 10.1016/j.ejor.2014.04.039

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().