Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{azarmehr_et_al:LIPIcs.ICALP.2023.14, author = {Azarmehr, Amir and Behnezhad, Soheil}, title = {{Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.14}, URN = {urn:nbn:de:0030-drops-180666}, doi = {10.4230/LIPIcs.ICALP.2023.14}, annote = {Keywords: Maximum Matching, Robust Communication Complexity, Edge Degree Constrained Subgraph} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Allan Borodin, Calum MacRury, and Akash Rakheja. Prophet Matching in the Probe-Commit Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 46:1-46:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2022.46, author = {Borodin, Allan and MacRury, Calum and Rakheja, Akash}, title = {{Prophet Matching in the Probe-Commit Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {46:1--46:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.46}, URN = {urn:nbn:de:0030-drops-171686}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.46}, annote = {Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bernstein_et_al:LIPIcs.ICALP.2022.20, author = {Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He}, title = {{Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {20:1--20:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.20}, URN = {urn:nbn:de:0030-drops-163611}, doi = {10.4230/LIPIcs.ICALP.2022.20}, annote = {Keywords: dynamic graph algorithm, adaptive adversary, spanner, sparsifier} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 77:1-77:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jambulapati_et_al:LIPIcs.ICALP.2022.77, author = {Jambulapati, Arun and Jin, Yujia and Sidford, Aaron and Tian, Kevin}, title = {{Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {77:1--77:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.77}, URN = {urn:nbn:de:0030-drops-164181}, doi = {10.4230/LIPIcs.ICALP.2022.77}, annote = {Keywords: bipartite matching, decremental matching, dynamic algorithms, continuous optimization, box-simplex games, primal-dual method} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Mohammad Roghani, Amin Saberi, and David Wajc. Beating the Folklore Algorithm for Dynamic Matching. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 111:1-111:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{roghani_et_al:LIPIcs.ITCS.2022.111, author = {Roghani, Mohammad and Saberi, Amin and Wajc, David}, title = {{Beating the Folklore Algorithm for Dynamic Matching}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {111:1--111:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.111}, URN = {urn:nbn:de:0030-drops-157077}, doi = {10.4230/LIPIcs.ITCS.2022.111}, annote = {Keywords: dynamic matching, dynamic graph algorithms, sublinear algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Allan Borodin, Calum MacRury, and Akash Rakheja. Secretary Matching Meets Probing with Commitment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{borodin_et_al:LIPIcs.APPROX/RANDOM.2021.13, author = {Borodin, Allan and MacRury, Calum and Rakheja, Akash}, title = {{Secretary Matching Meets Probing with Commitment}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {13:1--13:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.13}, URN = {urn:nbn:de:0030-drops-147067}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.13}, annote = {Keywords: Stochastic probing, Online algorithms, Bipartite matching, Optimization under uncertainty} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Chien-Chung Huang and François Sellier. Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2021.14, author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois}, title = {{Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {14:1--14:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.14}, URN = {urn:nbn:de:0030-drops-147072}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.14}, annote = {Keywords: Maximum Weight Matching, Submodular Function Maximization, Streaming, Matroid} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. Near-Optimal Schedules for Simultaneous Multicasts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 78:1-78:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{haeupler_et_al:LIPIcs.ICALP.2021.78, author = {Haeupler, Bernhard and Hershkowitz, D. Ellis and Wajc, David}, title = {{Near-Optimal Schedules for Simultaneous Multicasts}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {78:1--78:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.78}, URN = {urn:nbn:de:0030-drops-141471}, doi = {10.4230/LIPIcs.ICALP.2021.78}, annote = {Keywords: Packet routing, multicast, scheduling algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Amin Saberi and David Wajc. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{saberi_et_al:LIPIcs.ICALP.2021.109, author = {Saberi, Amin and Wajc, David}, title = {{The Greedy Algorithm Is not Optimal for On-Line Edge Coloring}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {109:1--109:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.109}, URN = {urn:nbn:de:0030-drops-141786}, doi = {10.4230/LIPIcs.ICALP.2021.109}, annote = {Keywords: Online algorithms, edge coloring, greedy, online matching} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic Online Metric Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2019.67, author = {Gupta, Anupam and Guruganesh, Guru and Peng, Binghui and Wajc, David}, title = {{Stochastic Online Metric Matching}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {67:1--67:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.67}, URN = {urn:nbn:de:0030-drops-106430}, doi = {10.4230/LIPIcs.ICALP.2019.67}, annote = {Keywords: stochastic, online, online matching, metric matching} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Mohsen Ghaffari and David Wajc. Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 13:1-13:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ghaffari_et_al:OASIcs.SOSA.2019.13, author = {Ghaffari, Mohsen and Wajc, David}, title = {{Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {13:1--13:8}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.13}, URN = {urn:nbn:de:0030-drops-100396}, doi = {10.4230/OASIcs.SOSA.2019.13}, annote = {Keywords: Streaming, Semi-Streaming, Space-Optimal, Matching} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{arar_et_al:LIPIcs.ICALP.2018.7, author = {Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, title = {{Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.7}, URN = {urn:nbn:de:0030-drops-90112}, doi = {10.4230/LIPIcs.ICALP.2018.7}, annote = {Keywords: Dynamic, Worst-case, Maximum Matching, Maximum Weight Matching} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-Dynamic Bin Packing with Little Repacking. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 51:1-51:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{feldkord_et_al:LIPIcs.ICALP.2018.51, author = {Feldkord, Bj\"{o}rn and Feldotto, Matthias and Gupta, Anupam and Guruganesh, Guru and Kumar, Amit and Riechers, S\"{o}ren and Wajc, David}, title = {{Fully-Dynamic Bin Packing with Little Repacking}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {51:1--51:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.51}, URN = {urn:nbn:de:0030-drops-90556}, doi = {10.4230/LIPIcs.ICALP.2018.51}, annote = {Keywords: Bin Packing, Fully Dynamic, Recourse, Tradeoffs} }
Feedback for Dagstuhl Publishing