Document Open Access Logo

On the Power of Advice and Randomization for Online Bipartite Matching

Authors Christoph Dürr, Christian Konrad, Marc Renault

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.37.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Author Details

Christoph Dürr
Christian Konrad
Marc Renault

Cite As Get BibTex

Christoph Dürr, Christian Konrad, and Marc Renault. On the Power of Advice and Randomization for Online Bipartite Matching. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.37

Abstract

While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bits that are set by an all-powerful oracle prior to the processing of the request sequence. Advice bits are at least as helpful as random bits, but how helpful are they? In this work, we investigate the power of advice bits and random bits for online maximum bipartite matching (MBM).

The well-known Karp-Vazirani-Vazirani algorithm [Karp, Vazirani and Vazirani 90] is an optimal randomized (1-1/e)-competitive algorithm for MBM that requires access to Theta(n log n) uniform random bits. We show that Omega(log(1/epsilon) n) advice bits are necessary and O(1/epsilon^5 n) sufficient in order to obtain a (1-epsilon)-competitive deterministic advice algorithm. Furthermore, for a large natural class of deterministic advice algorithms, we prove that Omega(log log log n) advice bits are required in order to improve on the 1/2-competitiveness of the best deterministic online algorithm, while it is known that O(log n) bits are sufficient [Böckenhauer, Komm, Královic and Královic 2011].

Last, we give a randomized online algorithm that uses cn random bits, for integers c >= 1, and a competitive ratio that approaches 1-1/e very quickly as c is increasing. For example if c = 10, then the difference between 1-1/e and the achieved competitive ratio is less than 0.0002.

Subject Classification

Keywords
  • On-line algorithms
  • Bipartite matching
  • Randomization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anna Adamaszek, Marc P. Renault, Adi Rosén, and Rob van Stee. Reordering buffer management with advice. In 11th International Workshop on Approximation and Online Algorithms (WAOA), pages 132-143, September 2013. Google Scholar
  2. Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc Renault, and Adi Rosén. Online bin packing with advice of small size. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS), pages 40-53. Springer International Publishing, August 2015. Google Scholar
  3. Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In Proceedings of the 18th Annual European Conference on Algorithms (ESA), pages 170-181. Springer-Verlag, 2010. Google Scholar
  4. Maria Paola Bianchi, Hans-Joachim Böckenhauer, Tatjana Brülisauer, Dennis Komm, and Beatrice Palano. Online minimum spanning tree with advice. In Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 195-207, January 2016. URL: http://dx.doi.org/10.1007/978-3-662-49192-8_16.
  5. Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80-87, March 2008. URL: http://dx.doi.org/10.1145/1360443.1360462.
  6. Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, and Andreas Sprock. The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci., 554:95-108, 2014. Google Scholar
  7. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. On the advice complexity of online problems. In Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra, editors, Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC), pages 331-340. Springer Berlin Heidelberg, December 2009. Google Scholar
  8. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theor. Comput. Sci., 527:61-72, 2014. Google Scholar
  9. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, and Richard Královič. On the advice complexity of the k-server problem. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), volume 6755 of Lecture Notes in Computer Science, pages 207-218. Springer Berlin Heidelberg, July 2011. URL: http://dx.doi.org/10.1007/978-3-642-22006-7_18.
  10. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. On the list update problem with advice. In Proceedings of the 8th International Conference on Language and Automata Theory and Applications (LATA), pages 210-221, March 2014. URL: http://dx.doi.org/10.1007/978-3-319-04921-2_17.
  11. Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz. Online bin packing with advice. Algorithmica, 74(1):507-527, 2016. URL: http://dx.doi.org/10.1007/s00453-014-9955-8.
  12. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 101-107, January 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.7.
  13. Stefan Dobrev, Rastislav Královič, and Dana Pardubská. How much information about the future is needed? In Proceedings of the 34th conference on Current trends in theory and practice of computer science (SOFSEM), pages 247-258, Berlin, Heidelberg, 2008. Springer-Verlag. Google Scholar
  14. Sebastian Eggert, Lasse Kliemann, Peter Munstermann, and Anand Srivastav. Bipartite matching in the semi-streaming model. Algorithmica, 63(1):490-508, 2011. Google Scholar
  15. Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theor. Comput. Sci., 412(24):2642-2656, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.08.007.
  16. Paul Erdös and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  17. Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 117-126, Washington, DC, USA, 2009. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2009.72.
  18. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982-991, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1347082.1347189.
  19. Edward F. Grove. Online bin packing with lookahead. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 430-436, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313651.313781.
  20. Sushmita Gupta, Shahin Kamali, and Alejandro López-Ortiz. On advice complexity of the k-server problem under sparse metrics. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 55-67, July 2013. URL: http://dx.doi.org/10.1007/978-3-319-03578-9_5.
  21. Magnús M. Halldórsson. Online coloring known graphs. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 917-918, Philadelphia, PA, USA, 1999. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=314500.315088.
  22. Magnús M. Halldórsson and Márió Szegedy. Lower bounds for on-line graph coloring. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 211-216, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=139404.139452.
  23. Shahin Kamali and Alejandro López-Ortiz. Better compression through better list update algorithms. In Proceedings of the Data Compression Conference (DCC), pages 372-381, March 2014. URL: http://dx.doi.org/10.1109/DCC.2014.86.
  24. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, New York, NY, USA, 1990. ACM. URL: http://dx.doi.org/10.1145/100216.100262.
  25. Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 7408 of Lecture Notes in Computer Science, pages 231-242. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32512-0_20.
  26. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC), pages 597-606, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993636.1993716.
  27. Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1285-1294. SIAM, 2011. URL: http://dl.acm.org/citation.cfm?id=2133036.2133134.
  28. Jesper W. Mikkelsen. Randomization can be as helpful as a glimpse of the future in online computation. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), July 2016. URL: http://arxiv.org/abs/1511.05886.
  29. Shuichi Miyazaki. On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett., 114(12):714-717, December 2014. URL: http://dx.doi.org/10.1016/j.ipl.2014.06.013.
  30. Marc P. Renault and Adi Rosén. On online algorithms with advice for the k-server problem. Theory Comput. Syst., 56(1):3-21, 2015. URL: http://dx.doi.org/10.1007/s00224-012-9434-z.
  31. Marc P. Renault, Adi Rosén, and Rob van Stee. Online algorithms with advice for bin packing and scheduling problems. Theor. Comput. Sci., 600:155-170, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.07.050.
  32. Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, February 1985. URL: http://dx.doi.org/10.1145/2786.2793.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact