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 it 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 1/2 and at most 2 13/16. For general graphs, the gap lies between 3 and 3 5/16. A fully polynomial approximation scheme is also presented for the problem on a tree, thus generalizing a well-known result for the knapsack problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.
P. Berman and M. Karpinksi, “On some tighter inapproximability results”, Proc. 26 th Int. Coll. on Automota, Languages, and Programming, pp200–209, 1999.
A. Chakrabarti, C. Chekuri, A. Gupta and A. Kumar, “Approximation algorithms for the unsplittable flow problem”, manuscript, September 2001.
C. Chekuri and S. Khanna, “A PTAS for the Multiple Knapsack Problem”, Proc. 11th SODA, 2000.
C. Chekuri, Personal Communication, November 2000.
Y. Dinitz, N. Garg and M. Goemans, “On the Single-Source Unsplittable Flow Problem”, Combinatorica, 19, pp17–41, 1999.
J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices”, Journal of Research of the Natuional Bureau of Standards (B), 69, pp125–30, 1965.
N. Garg, V.V. Vazirani and M. Yannakakis, “Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees with Applications to Matching and Set Cover”, Algorithmica 18, pp3–20, 1997.
A.J. Hoffman and J.B. Kruskal, “Integral boundary points of convex polyhedra”, in H.W. Kuhn and A.W. Tucker eds., Linear Inequalities and Related Systems, Princeton University Press, pp223–246, 1956.
O.H. Ibarra and C.E. Kim, “Fast approximation for the knapsack and sum of subset problems”, Journal of the ACM, 22, pp463–468, 1975.
C.H. Papadimitriou, Computational Complexity, Addison Wesley, 1994.
D. Shmoys and É. Tardos, “An approximation algorithm for the generalized assignment problem”, Mathematical Programming A, 62, pp461–474, 1993.
L. Trevisan, “Non-approximability Results for Optimization Problems on Bounded Degree Instances”, Proc. 33rd STOC, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shepherd, B., Vetta, A. (2002). The Demand Matching Problem. In: Cook, W.J., Schulz, A.S. (eds) Integer Programming and Combinatorial Optimization. IPCO 2002. Lecture Notes in Computer Science, vol 2337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47867-1_32
Download citation
DOI: https://doi.org/10.1007/3-540-47867-1_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43676-8
Online ISBN: 978-3-540-47867-6
eBook Packages: Springer Book Archive