Abstract
We study the following generalization of the maximum matching problem in general graphs: Given a simple non-directed graph G = (V,E) and a partition of the edges into k classes (i.e. E = E 1 ∪ ⋯ ∪ E k ), we would like to compute a matching M on G of maximum cardinality or profit, such that |M ∩ E j | ≤ w j for every class E j . Such problems were first studied in the context of network design in [17]. We study the problem from a linear programming point of view: We provide a polynomial time \(\frac{1}{2}\)-approximation algorithm for the weighted case, matching the integrality gap of the natural LP formulation of the problem. For this, we use and adapt the technique of approximate convex decompositions [19] together with a different analysis and a polyhedral characterization of the natural linear program to derive our result. This improves over the existing \(\frac{1}{2}\), but with additive violation of the color bounds, approximation algorithm [14].
Part of this work was done while the author was a PhD student at IDSIA.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bampas, E., Pagourtzis, A., Potika, K.: An experimental study of maximum profit wavelength assignment in wdm rings. Networks 57(3), 285–293 (2011)
Berger, A., Bonifaci, V., Grandoni, F., Schäfer, G.: Budgeted matching and budgeted matroid intersection via the gasoline puzzle. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 273–287. Springer, Heidelberg (2008)
Berman, P.: A d/2 approximation for maximum weight independent set in d-claw free graphs. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 214–219. Springer, Heidelberg (2000)
Caragiannis, I.: Wavelength management in wdm rings to maximize the number of connections. SIAM J. Discrete Math. 23(2), 959–978 (2009)
Carathéodory, C.: Über den variabilitätsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rendiconti del Circolo Matematico di Palermo 32, 193–217 (1911)
Chan, Y.H., Lau, L.C.: On linear and semidefinite programming relaxations for hypergraph matching. Math. Program. 135(1-2), 123–148 (2012)
Chekuri, C., Vondrák, J., Zenklusen, R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In: SODA, pp. 1080–1097 (2011)
Edmonds, J.: Maximum matching and a polyhedron with 0,1 vertices. J. of Res. the Nat. Bureau of Standards 69B, 125–130 (1965)
Fürer, M., Yu, H.: Approximate the k-set packing problem by local improvements. In: ISCO-3rd International Symbosium on Combinatorial Optimization, Lisboa, Portugal, March 5-7, Lisboa, Portugal, March 5-7 (2014)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
Grandoni, F., Ravi, R., Singh, M.: Iterative rounding for multi-objective optimization problems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 95–106. Springer, Heidelberg (2009)
Grandoni, F., Zenklusen, R.: Approximation schemes for multi-budgeted independence systems. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol. 6346, pp. 536–548. Springer, Heidelberg (2010)
Mastrolilli, M., Stamoulis, G.: Constrained matching problems in bipartite graphs. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 344–355. Springer, Heidelberg (2012)
Mastrolilli, M., Stamoulis, G.: Bi-criteria approximation algorithms for restricted matchings. Theoretical Computer Science 540-541, 115–132 (2014)
Monnot, J.: The labeled perfect matching in bipartite graphs. Inf. Process. Lett. 96(3), 81–88 (2005)
Nomikos, C., Pagourtzis, A., Zachos, S.: Minimizing request blocking in all-optical rings. In: IEEE INFOCOM (2003)
Nomikos, C., Pagourtzis, A., Zachos, S.: Randomized and approximation algorithms for blue-red matching. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 715–725. Springer, Heidelberg (2007)
Papadimitriou, C.H., Yannakakis, M.: The complexity of restricted spanning tree problems. J. ACM 29(2), 285–309 (1982)
Parekh, O.: Iterative packing for demand and hypergraph matching. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 349–361. Springer, Heidelberg (2011)
Yuster, R.: Almost exact matchings. Algorithmica 63(1-2), 39–50 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stamoulis, G. (2014). Approximation Algorithms for Bounded Color Matchings via Convex Decompositions. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds) Mathematical Foundations of Computer Science 2014. MFCS 2014. Lecture Notes in Computer Science, vol 8635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44465-8_53
Download citation
DOI: https://doi.org/10.1007/978-3-662-44465-8_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44464-1
Online ISBN: 978-3-662-44465-8
eBook Packages: Computer ScienceComputer Science (R0)