ISSN:
1436-5057
Schlagwort(e):
90C10
;
Matching problem
;
assignment problem
;
computational results
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Beschreibung / Inhaltsverzeichnis:
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.
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02240072
Permalink
