Skip to main content
SpringerLink
Log in

On the use of optimal fractional matchings for solving the (integer) matching problem

Über die Anwendung optimaler Fractional Matchings zur Lösung des (ganzzahligen) Matching-Problems

  • Short Communications
  • Published:
Computing Aims and scope Submit manuscript

Abstract

We show how optimal fractional matchings can be used to start the shortest augmenting path method for solving the (integer) matching problem. Computational results are presented which indicate that this start procedure is highly efficient, i.e. it is fast and reduces the amount of work for the shortest augementing path method significantly such that the overall computing time is reduced drastically.

Zusammenfassung

Wir zeigen wie optimale „Fractional Matchings”, d. h. optimale Lösungen der LP-Relaxation des Matching-Problems, benutzt werden können, um Ausgangslösungen für die kürzeste erweiternde Wege-Methode zur Lösung des Matching-Problems zu konstruieren. Numerische Untersuchungen zeigen, daß diese Startprozedur höchst effizient ist und den Aufwand für den eigentlichen Matching-Algorithmus signifikant reduziert, so daß die Gesamtrechenzeit drastisch reduziert wird.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

References

  1. Balinski, M.: Integer programming: methods, uses, computation. In: Mathematics of the Decision Sciences (G. B. Dantzig and A. F. Veinott, eds.) Part I, pp. 179–256. American Mathematical Society Providence (1968).

  2. Burkard, R. E., Derigs, U.: Assignment and matching problems: solution methods with FORTRAN-Programs. Springer Lecture Notes in Mathematical Systems No. 184 (1980).

  3. Derigs, U.: A shortest augmenting path method for solving minimal perfect matching problems. Networks11, 379–390 (1981).

    Google Scholar 

  4. Derigs, U.: The shortest augmenting path method for solving assignment problems — motivation and computational experience. Report No. 82328, Institut für Ökonometrie und Operations Research, Universität Bonn, 1984 (to appear in Annals of Operations Research).

  5. Edmonds, J.: Maximum matching and a polyhedron with 0,1 vertices. J. Res. Natl. Bur. Stand.69B, 125–130 (1965).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Lehrstuhl für Betriebswirtschaftslehre VII, insbesondere Betriebsinformatik, Universität Bayreuth, Postfach 3008, D-8580, Bayreuth, Germany

    U. Derigs

  2. Institut für Ökonometrie und Operations Research Abteilung Operations Research, Rheinische Friedrich-Wilhelms-Universität Bonn, Nassestrasse 2, D-5300, Bonn 1, Germany

    A. Metz

Authors
  1. U. Derigs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Metz
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, Federal Republic of Germany and Research Grant (DFG) De 352/1-1.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Derigs, U., Metz, A. On the use of optimal fractional matchings for solving the (integer) matching problem. Computing 36, 263–270 (1986). https://doi.org/10.1007/BF02240072

Download citation

  • Received:

  • Issue Date:

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

AMS Subject Classification

Key words

Search

Navigation