Fractional covers for forests and matchings |
| |
Authors: | Manfred W. Padberg Laurence A. Wolsey |
| |
Affiliation: | (1) CORE, 34 Voie du Roman Pays, B-1348 Louvain-la-Neuve, Belgium |
| |
Abstract: | We give polynomial algorithms for the fractional covering problems for forests andb-matchings: min{1·y: yA≥w,y≥0} whereA is a matrix whose rows are the incidence vectors of forests/b-matchings respectively. It is shown that each problem can be solved by a series of max-flow/min-cut calculations, and hence the use of the ellipsoid algorithm to guarantee a polynomial algorithm can be avoided. Visiting professor at the European Institute for Advanced Studies in Management in Brussels and at CORE. Supported in part by the CIM. On leave from New York University, New York, NY 10006. |
| |
Keywords: | Fractional Covers Forests Matchings |
本文献已被 SpringerLink 等数据库收录! |