Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Tight integral duality gap in the Chinese Postman problem

  • Published:
Mathematical Programming Submit manuscript

Abstract

LetG = (V, E) be a graph and letw be a weight functionw:E →Z +. Let\(T \subseteq V\) be an even subset of the vertices ofG. AT-cut is an edge-cutset of the graph which dividesT into two odd sets. AT-join is a minimal subset of edges that meets everyT-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 weightT-join and the maximum weight integral packing ofT-cuts. This difference is called the (T-join) integral duality gap. Letτ w be the minimum weight of aT-join, and letv w be the maximum weight of an integral packing ofT-cuts. IfF is a non-empty minimum weightT-join, andn F is the number of components ofF, then we prove thatτ w —v w ≤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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (Elsevier, New York, 1976).

    Google Scholar 

  2. W.H. Cunningham and A.B. Marsh III, “A primal algorithm for optimum matching,”Mathematical Programming Study 8 (1978) 50–72.

    Google Scholar 

  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.

    Google Scholar 

  4. J. Edmonds and E.L. Johnson, “Matching, Euler tours and the Chinese Postman,”Mathematical Programming 5 (1973) 88–129.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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).

    Google Scholar 

  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).

    Google Scholar 

  9. L. Lovász, “2-mathings and 2-covers of hypergraphs,”Acta Mathematica, Academiae Scientiarem Hungaricae 26 (1975) 433–444.

    Google Scholar 

  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).

    Google Scholar 

  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.]

    Google Scholar 

  12. A. Sebö, “On the structure of odd-joins,”Journal of Combinatorial Theory, Series B 49 (1990) 10–39.

    Google Scholar 

  13. P.D. Seymour, “The matroids with the max-flow min-cut property,”Journal of Combinatorial Theory, Series B 23 (1977) 189–222.

    Google Scholar 

  14. P.D. Seymour, “Matroids and multicommodity flows,”European Journal of Combinatorics 2 (1981) 257–290.

    Google Scholar 

  15. P.D. Seymour, “On odd cuts and plane multicommodity flows,” in:Proceedings of the London Mathematical Society (3) 42 (1981) 178–192.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Technion — Israel Institute of Technology, Haifa, Israel

    Ephraim Korach

  2. Faculty of Industrial and Management Engineering, Technion — Israel Institute of Technology, Haifa, Israel

    Michal Penn

Authors
  1. Ephraim Korach
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michal Penn
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research of the first author was partially supported by Technion V.P.R. Fund — C. and J. Bishop Research Fund, and Argentinian Research Fund.

Part of this work was done as part of the author's D.Sc. Thesis in the Faculty of Industrial and Management Engineering, Technion — Israel Institute of Technology, Haifa. Research of this author was partially supported by Technion V.P.R. Fund — The Baltimore Fund for Industrial Engineering and Management Research.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Korach, E., Penn, M. Tight integral duality gap in the Chinese Postman problem. Mathematical Programming 55, 183–191 (1992). https://doi.org/10.1007/BF01581198

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01581198

Key words

Search

Navigation