×

Tight integral duality gap in the Chinese postman problem. (English) Zbl 0767.90088

Let \(G=(V,E)\) be a graph and let \(w\) be a weight function \(w:E\to Z^ +\). Let \(T\subseteq V\) be an even subset of the vertices of \(G\). A \(T\)- cut is an edge-cutset of the graph which divides \(T\) into two odd sets. A \(T\)-join is a minimal subset of edges that meets every \(T\)-cut (a generalization of solutions to the Chinese Postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weight \(T\)-join and the maximum weight integral packing of \(T\)-cuts. This difference is called the \((T\)-join) integral duality gap. Let \(\tau_ w\) be the minimum weight of a \(T\)-join, and let \(\nu_ w\) be the maximum weight of an integral packing of \(T\)-cuts. If \(F\) is a non-empty minimum weight \(T\)-join, and \(n_ F\) is the number of components of \(F\), then we prove that \(\tau_ w-\nu_ w\leq n_ F- 1\).
This result unifies and generalizes Fulkerson’s result for \(| T|=2\) and Seymour’s result for \(| T|=4\). For a certain integral multicommodity flow problem in the plane, which was recently proved to be \(NP\)-complete, the above result gives a solution such that for every commodity the flow is less than the demand by at most one unit.

MSC:

90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (Elsevier, New York, 1976). · Zbl 1226.05083
[2] W.H. Cunningham and A.B. Marsh III, ”A primal algorithm for optimum matching,”Mathematical Programming Study 8 (1978) 50–72. · Zbl 0409.90081
[3] J. Edmonds and E.L. Johnson, ”Matching a well-solved class of integer linear programs”, in: R. Guy, H. Hanani, N. Sauer and J. Schonheim, eds.,Combinatorial Structures and Their Applications (Gordon and Breach, New York, 1970) pp. 89–92. · Zbl 0258.90032
[4] J. Edmonds and E.L. Johnson, ”Matching, Euler tours and the Chinese Postman,”Mathematical Programming 5 (1973) 88–129. · Zbl 0281.90073 · doi:10.1007/BF01580113
[5] S. Even, A. Itai and A. Shamir, ”On the complexity of time table and multicommodity flow problems,”SIAM Journal on Computing 5 (1976) 691–703. · Zbl 0358.90021 · doi:10.1137/0205048
[6] D.R. Fulkerson, ”Networks, frames and blocking systems,” in: G.B. Dantzig and A.F. Veinott, eds.,Mathematics of the Decision Sciences, Part I (American Mathematical Society, Providence, RI 1968) pp. 303–334. · Zbl 0182.53402
[7] E. Korach, ”Packing ofT-cuts, and other aspects of dual integrality,” Ph.D. thesis, Department of Combinatorics and Optimization, University of Waterloo (Waterloo, Ont., 1982).
[8] E. Korach and M. Penn, ”Tight integral duality gap in the Chinese Postman problem,” Technical Report No. 360, Computer Science Department, Technion – Israel Institute of Technology (Haifa, Israel, 1985). · Zbl 0767.90088
[9] L. Lovász, ”2-mathings and 2-covers of hypergraphs,”Acta Mathematica, Academiae Scientiarem Hungaricae 26 (1975) 433–444. · Zbl 0339.05123 · doi:10.1007/BF01902352
[10] M. Middendorf and F. Pfeiffer, ”On the complexity of the disjoint path problem,” Report No. 89585-OR, Institut für Operations Research, Universität Bonn (Bonn, 1989). · Zbl 0770.68072
[11] M. Penn, ”On integral duality gap in the Chinese Postman problem, plane multi-commodity flow and weakly bipartite graphs,” D.Sc. thesis, Department of Industrial and Management Engineering, Technion – Israel Institute of Technology (Haifa, Israel, 1987). [In Hebrew.]
[12] A. Sebö, ”On the structure of odd-joins,”Journal of Combinatorial Theory, Series B 49 (1990) 10–39. · Zbl 0638.05032 · doi:10.1016/0095-8956(90)90062-5
[13] P.D. Seymour, ”The matroids with the max-flow min-cut property,”Journal of Combinatorial Theory, Series B 23 (1977) 189–222. · Zbl 0375.05022 · doi:10.1016/0095-8956(77)90031-4
[14] P.D. Seymour, ”Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290. · Zbl 0479.05023
[15] P.D. Seymour, ”On odd cuts and plane multicommodity flows,” in:Proceedings of the London Mathematical Society (3) 42 (1981) 178–192. · Zbl 0447.90026 · doi:10.1112/plms/s3-42.1.178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.