More Web Proxy on the site http://driver.im/

research-article

SIGACT News Online Algorithms Column 35: 2019 in review

Authors:

Sören Schmitt,

Rob van SteeAuthors Info & Claims

ACM SIGACT News, Volume 50, Issue 4

Pages 77 - 92

https://doi.org/10.1145/3374857.3374871

Published: 04 December 2019 Publication History

Abstract

In this column, we will discuss some papers in online algorithms that appeared in 2019. As usual, we make no claim at complete coverage here, and have instead made a selection. If we have unaccountably missed your favorite paper and you would like to write about it or about any other topic in online algorithms, please don't hesitate to contact us!

References

[1]

Spyros Angelopoulos, Christoph Durr, and Shendan Jin. Best-Of-Two-Worlds Analysis of Online Search. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs), pages 7:1{7:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[2]

C. J. Argue, S--ebastien Bubeck, Michael B. Cohen, Anupam Gupta, and Yin Tat Lee. A nearly-linear bound for chasing nested convex bodies. In Chan [19], pages 117{122.

[3]

Norbert Ascheuer, Sven Oliver Krumke, and Jorg Rambau. Online dial-a-ride problems: Minimizing the completion time. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS '00, pages 639{650, London, UK, UK, 2000. Springer- Verlag.

[4]

Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Edge weighted online windowed matching. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24--28, 2019., pages 729{742. ACM, 2019.

Digital Library

[5]

Yossi Azar, Yuval Emek, Rob van Stee, and Danny Vainstein. The price of clustering in bin-packing with applications to bin-packingwith delays. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '19, pages 1{10, New York, NY, USA, 2019. ACM.

Digital Library

[6]

Yossi Azar and Noam Touitou. General framework for metric optimization problems with delay or with deadlines. CoRR, abs/1904.07131, 2019.

[7]

Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9- 12, 2019, Patras, Greece, volume 132 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019.

[8]

Evripidis Bampis, Bruno Escoer, Kevin Schewior, and Alexandre Teiller. Online Multistage Subset Maximization Problems. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1{11:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[9]

Nikhil Bansal, Martin Bohm, Marek Eli--as, Grigorios Koumoutsos, and Seeun William Umboh. Nested convex bodies are chaseable. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1253{1260, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics.

[10]

Nikhil Bansal, Marek Elias, Grigorios Koumoutsos, and Jesper Nederlof. Competitive algorithms for generalized k-server in uniform metrics. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 992{1001, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics.

[11]

Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online bin covering with limited migration. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9--11, 2019, Munich/Garching, Germany., volume 144 of LIPIcs, pages 18:1{18:14. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2019.

[12]

Marcin Bienkowski, Lukasz Jez, and Pawel Schmidt. Slaying hydrae: Improved bounds for generalized k-server in uniform metrics. CoRR, abs/1810.00580, 2018.

[13]

Alexander Birx and Yann Disser. Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1{15:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[14]

Alexander Birx, Yann Disser, and Kevin Schewior. Improved Bounds for Open Online Dial-a- Ride on the Line. In Dimitris Achlioptas and L--aszl--o A. V--egh, editors, Approximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1{ 21:22, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[15]

Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen. Online bin covering with advice. In Friggstad et al. [29], pages 225{238.

[16]

S--ebastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In Diakonikolas et al. [24], pages 3{16.

[17]

S--ebastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Charikar and Cohen [20], pages 861{868.

[18]

Niv Buchbinder, Anupam Gupta, Marco Molinaro, and Joseph (Se) Naor. k-servers with a smile: Online algorithms via projections. In Chan [19], pages 98{116.

[19]

Timothy M. Chan, editor. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6--9, 2019. SIAM, 2019.

[20]

Moses Charikar and Edith Cohen, editors. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23--26, 2019. ACM, 2019.

Digital Library

[21]

Shuchi Chawla, J. Benjamin Miller, and Yifeng Teng. Pricing for online resource allocation: Intervals and paths. In Chan [19], pages 1962{1981.

[22]

Christian Coester and Elias Koutsoupias. The online k-taxi problem. In Charikar and Cohen 20, pages 1136{1147.

[23]

Ilan Reuven Cohen, Binghui Peng, and David Wajc. Tight bounds for online edge coloring. CoRR, abs/1904.09222, 2019.

[24]

Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25--29, 2018. ACM, 2018.

Digital Library

[25]

Yuval Emek, Adam Goldbraikh, and Erez Kantor. Online Disjoint Set Cover Without Prior Knowledge. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceed- ings in Informatics (LIPIcs), pages 44:1{44:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl{ Leibniz-Zentrum fuer Informatik.

[26]

Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved bounds for online preemptive matching. In Natacha Portier and Thomas Wilke, editors, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, volume 20 of LIPIcs, pages 389{399. Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 2013.

[27]

S--andor P. Fekete, Sven von Hoveling, and Christian Sche er. Online circle packing. In Friggstad et al. [29], pages 366{379.

[28]

Joel Friedman and Nathan Linial. On convex body chasing. Discrete Comput. Geom., 9(3):293{ 321, December 1993.

Digital Library

[29]

Zachary Friggstad, Jorg-Rudiger Sack, and Mohammad R. Salavatipour, editors. Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5--7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science. Springer, 2019.

Digital Library

[30]

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online matching with general arrivals. CoRR, abs/1904.08255, 2019.

[31]

Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla. Non-clairvoyant precedence constrained scheduling. In Baier et al. [7], pages 63:1{63:14.

[32]

Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. Dynamic dictionary matching in the online model. In Friggstad et al. [29], pages 409{422.

[33]

Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic online metric matching. In Baier et al. [7], pages 67:1{67:14.

[34]

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Elastic caching. In Chan [19], pages 143{156.

[35]

Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Online and stochastic survivable network design. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Sym- posium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 685{694. ACM, 2009.

[36]

Xin Han, Yasushi Kawase, Kazuhisa Makino, and Haruki Yokomaku. Online knapsack problems with a resource bu er. In 30th International Symposium on Algorithms and Computation (ISAAC 2019), 2019.

[37]

Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Diakonikolas et al. [24], pages 17{29.

[38]

Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, XiaoweiWu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In Chan [19], pages 2875{2886.

[39]

Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990, Baltimore, Maryland, USA, pages 352{358. ACM, 1990.

[40]

Thomas Kesselheim, Klaus Radke, Andreas Tonnis, and Berthold Vocking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2--4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science, pages 589{600. Springer, 2013.

[41]

Andrew P. Kosoresow. Design and analysis of online algorithms for mobile server applications. PhD thesis, Stanford University, 1996.

[42]

Sven Oliver Krumke. Online Optimization: Competitive Analysis and Beyond. Habilitation thesis, Technische Universitat Berlin, 2002.

[43]

Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10--12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 50:1{50:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019.

[44]

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing on a Star Network: On-Line Scheduling with k Servers. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1{51:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[45]

Joseph (Se) Naor, Seeun William Umboh, and David P. Williamson. Tight bounds for online weighted tree augmentation. In Baier et al. [7], pages 88:1{88:14.

[46]

David Naori and Danny Raz. Online multidimensional packing problems in the random-order model. In 30th International Symposium on Algorithms and Computation (ISAAC 2019), 2019.

[47]

A. Pananjady, V. K. Bagaria, and R. Vaze. The online disjoint set cover problem and its applications. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1221{1229, April 2015.

[48]

Enoch Peserico. Paging with Dynamic Memory Capacity. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1{56:18, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik.

[49]

Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Klaus Jansen, Claire Mathieu, Jos--e D. P. Rolim, and Chris Umans, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7--9, 2016, Paris, France, volume 60 of LIPIcs, pages 18:1{18:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.

[50]

Rebecca Reienhauser. An optimal truthful mechanism for the online weighted bipartite matching problem. In Chan [19], pages 1982{1993.

[51]

Pavel Vesel--y, Marek Chrobak, Lukasz Je_z, and Jir Sgall. A-competitive algorithm for scheduling packets with deadlines. In Chan [19], pages 123{142.

[52]

Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Magn--us M. Halld--orsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6--10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 1070{1081. Springer, 2015.

Cited By

Bertazzi LChagas GCoelho LLaganà DVocaturo F(2025)Online algorithms for the multi-vehicle inventory-routing problem with real-time demandsTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104892170(104892)Online publication date: Jan-2025
https://doi.org/10.1016/j.trc.2024.104892
Barba ABertazzi LGolden B(2024)Competitive Analysis of Algorithms for an Online Distribution ProblemAlgorithms10.3390/a1706023717:6(237)Online publication date: 3-Jun-2024
https://doi.org/10.3390/a17060237

SIGACT News Online Algorithms Column 35: 2019 in review
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

SIGACT News Online Algorithms Column 34: 2018 in review

In this column, I will discuss some papers in online algorithms that appeared in 2018. It is very nice to see many good papers on this topic appearing year after year. I make no claim at complete coverage here, and have instead made a selection.

As ...
SIGACT News Online Algorithms Column 42

For this issue, I am pleased to present a tutorial by Will Ma on using randomized rounding to design online policies. Randomized rounding has of course been used extensively in the design of approximation algorithms and also to approximately solve ...
SIGACT news online algorithms column 24: 2014 so far

In this column, I will discuss some recent papers in online algorithms. It is pleasing to see there were a number of papers about online algorithms in the top conferences this year. If I have missed your paper and you want to write about it or about any ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 50, Issue 4

December 2019

114 pages

ISSN:0163-5700

DOI:10.1145/3374857

Editor:
Stephen Fenner
University of South Carolina

Issue’s Table of Contents

Copyright © 2019 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 December 2019

Published in SIGACT Volume 50, Issue 4

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
204
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bertazzi LChagas GCoelho LLaganà DVocaturo F(2025)Online algorithms for the multi-vehicle inventory-routing problem with real-time demandsTransportation Research Part C: Emerging Technologies10.1016/j.trc.2024.104892170(104892)Online publication date: Jan-2025
https://doi.org/10.1016/j.trc.2024.104892
Barba ABertazzi LGolden B(2024)Competitive Analysis of Algorithms for an Online Distribution ProblemAlgorithms10.3390/a1706023717:6(237)Online publication date: 3-Jun-2024
https://doi.org/10.3390/a17060237

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents