The Demand-Matching Problem
Authors:
- 1 August 2007
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 32 (3) , 563-578
Abstract
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 bv. 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.Keywords
This publication has 19 references indexed in Scilit:
- A Polynomial Time Approximation Scheme for the Multiple Knapsack ProblemSIAM Journal on Computing, 2005
- Approximating disjoint-path problems using packing integer programsMathematical Programming, 2004
- Multirate Rearrangeable Clos Networks and a Generalized Edge-Coloring Problem on Bipartite GraphsSIAM Journal on Computing, 2003
- Approximating the single source unsplittable min-cost flow problemMathematical Programming, 2002
- A unified approach to approximating resource allocation and schedulingJournal of the ACM, 2001
- Approximation Algorithms for Single-Source Unsplittable FlowSIAM Journal on Computing, 2001
- On the Single-Source Unsplittable Flow ProblemCombinatorica, 1999
- On Multirate Rearrangeable Clos NetworksSIAM Journal on Computing, 1998
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965