Abstract
We present efficient distributed δ-approximation algorithms for fractional packing and maximum weighted b-matching in hypergraphs, where δ is the maximum number of packing constraints in which a variable appears (for maximum weighted b-matching δ is the maximum edge degree — for graphs δ= 2). (a) For δ= 2 the algorithm runs in O(logm) rounds in expectation and with high probability. (b) For general δ, the algorithm runs in O(log2 m) rounds in expectation and with high probability.
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
Bar-Yehuda, R.: One for the price of two: A unified approach for approximating covering problems. Algorithmica 27(2), 131–144 (2000)
Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: a unified framework for approximation algorithms. ACM Computing Surveys 36(4), 422–463 (2004)
Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local-ratio technique. SIAM Journal on Discrete Mathematics 19(3), 762–797 (2005)
Czygrinow, A., Hańćkowiak, M., Szymańska, E.: A fast distributed algorithm for approximating the maximum matching. In: The twelfth European Symosium on Algorithms, pp. 252–263 (2004)
Edmonds, J.: Paths, trees, and flowers. Canadian Journal of Mathematics 17, 449–467 (1965)
Edmonds, J., Johnson, E.L.: Matching: A well-solved class of integer linear programs. In: Combinatorial Structures and Their Applications, pp. 89–92 (1970)
Hoepman, J.H.: Simple distributed weighted matchings. Arxiv preprint cs.DC/0410047 (2004)
Hougardy, S., Vinkemeier, D.E.: Approximating weighted matchings in parallel. Information Processing Letters 99(3), 119–123 (2006)
Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters 22, 77–80 (1986)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York (1972)
Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: The forty-eighth IEEE symposium on Foundations of Computer Science, pp. 494–504 (2007)
Koufogiannakis, C., Young, N.E.: Distributed and parallel algorithms for weighted vertex cover and other covering problems. In: The twenty-eighth ACM symposium on Principles of Distributed Computing (2009)
Koufogiannakis, C., Young, N.E.: Greedy Δ-approximation algorithm for covering with arbitrary constraints and submodular cost. In: The thirty-sixth International Colloquium on Automata, Languages and Programming. LNCS, vol. 5555, pp. 634–652. Springer, Heidelberg (2009), http://arxiv.org/abs/0807.0644
Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: The seventeenth ACM-SIAM Symposium on Discrete Algorithm, pp. 980–989 (2006)
Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. In: The twetwenty-second ACM symposium on Principles of Distributed Computing, pp. 25–32 (2003)
Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13(4), 441–454 (1993)
Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. In: The 12th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 129–136 (2008)
Lotker, Z., Patt-Shamir, B., Rosén, A.: Distributed approximate matching. In: The 26th ACM symposium on Principles Of Distributed Computing, pp. 167–174 (2007)
Müller-Hannemann, M., Schwartz, A.: Implementing weighted b-matching algorithms: Towards a flexible software design. In: Goodrich, M.T., McGeoch, C.C. (eds.) ALENEX 1999. LNCS, vol. 1619, pp. 18–36. Springer, Heidelberg (1999)
Nieberg, T.: Local, distributed weighted matching on general and wireless topologies. In: The 5th ACM Joint Workshop on the Foundations of Mobile Computing, DIALM-POMC, pp. 87–92 (2008)
Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics (2000)
Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. Information Processing Letters 76(1-2), 13–17 (2000)
Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: The 18th international symposium on Distributed Computing, pp. 335–348 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koufogiannakis, C., Young, N.E. (2009). Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)