This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Shepherd, F. B. Articles by Vetta, A. Search for Related Content

The Demand-Matching Problem

Bell Laboratories, 600 Mountain Avenue, Murray Hill, New Jersey 07974
Department of Mathematics and Statistics, McGill University, Burnside Hall, 805 Sherbrooke W., Montreal, Quebec, Canada
bshep{at}bell-labs.com, http://cm.bell-labs.com/cm/ms/who/bshep/
vetta{at}math.mcgill.ca, http://www.math.mcgill.ca/vetta/

We examine formulations for the well-known b-matching problem in the presence of integer demands on the edges. A subset M of edges is feasible if for each node v the total demand of edges in M incident to v is at most b_v. We examine the system of star inequalities for this problem. This system yields an exact linear description for b-matchings in bipartite graphs. For the demand version, we show that the integrality gap for this system is at least 2.5 and at most 2.764. For general graphs, the gap lies between 3 and 3.264. We also describe a 3-approximation algorithm (2.5 for bipartite graphs) for the cardinality version of the problem. A fully polynomial approximation scheme is also presented for the problem on a tree, thus generalising a well-known result for the knapsack problem. Recently, the notion of demand matching has arisen in the design of Clos network switches.

Key Words: b-matching; linear programming; integrality gap; approximation algorithm
History: Received: January 14, 2004; revision received: April 20, 2006;