A polynomial algorithm for b-matchings: An alternative approach (Q1109690)

A b-matching of a given graph G is an assignment of integer weights to the edges of G so that the sum of the weights on the edges incident with a vertex v is at most \(b_ v\) (b denotes the vectors of \(b_ v's)\). When \(b_ v=1\) for all vertices v in G, then b-matchings are the usual matchings. The b-matching problem asks for a b-matching of maximum cost where the edges of G have been assigned costs and the cost of a b- matching is the sum of the weights times the costs. We do not assume G to be bipartite. We present a polynomial algorithm for the b-matching problem differing from the algorithm of \textit{W. H. Cunningham} and \textit{A. B. Marsh} [Math. Program. Study 8, 50-72 (1978; Zbl 0409.90081)]. In fact, the new algorithm is strongly polynomial using the new strongly polynomial minimum cost flow algorithm of \textit{E. Tardos} [Combinatorica 5, 247-255 (1985; Zbl 0596.90030)] (we actually use the algorithm of \textit{J. B. Orlin} [``Genuinely polynomial simplex and nonsimplex algorithms for the minimum cost flow problem'', Centrum for Wiskunde en Informatica, Stichting Mathematisch Centrum OS, No.8504 (1985)]) to obtain a half- integral optimal solution. An integral solution (close to being optimal) is obtained from it which is used as input to the b-matching algorithm of \textit{W. R. Pulleyblank} [``Faces of matching polyhedra'', Ph. D. Thesis, Dept. of Combinatorics and Optimization, Univ. of Waterloo (1973)].