Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15, author = {Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny}, title = {{List Update with Delays or Time Windows}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {15:1--15:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.15}, URN = {urn:nbn:de:0030-drops-201583}, doi = {10.4230/LIPIcs.ICALP.2024.15}, annote = {Keywords: Online, List Update, Delay, Time Window, Deadline} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kobayashi_et_al:LIPIcs.ICALP.2024.100, author = {Kobayashi, Yusuke and Terao, Tatsuya}, title = {{Subquadratic Submodular Maximization with a General Matroid Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {100:1--100:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.100}, URN = {urn:nbn:de:0030-drops-202437}, doi = {10.4230/LIPIcs.ICALP.2024.100}, annote = {Keywords: submodular maximization, matroid constraint, approximation algorithm, rounding algorithm, query complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg. On the Cut-Query Complexity of Approximating Max-Cut. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 115:1-115:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{plevrakis_et_al:LIPIcs.ICALP.2024.115, author = {Plevrakis, Orestis and Ragavan, Seyoon and Weinberg, S. Matthew}, title = {{On the Cut-Query Complexity of Approximating Max-Cut}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {115:1--115:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.115}, URN = {urn:nbn:de:0030-drops-202587}, doi = {10.4230/LIPIcs.ICALP.2024.115}, annote = {Keywords: query complexity, maximum cut, approximation algorithms, graph sparsification} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Raghuvansh R. Saxena, Santhoshini Velusamy, and S. Matthew Weinberg. An Improved Lower Bound for Matroid Intersection Prophet Inequalities. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{saxena_et_al:LIPIcs.ITCS.2023.95, author = {Saxena, Raghuvansh R. and Velusamy, Santhoshini and Weinberg, S. Matthew}, title = {{An Improved Lower Bound for Matroid Intersection Prophet Inequalities}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.95}, URN = {urn:nbn:de:0030-drops-175986}, doi = {10.4230/LIPIcs.ITCS.2023.95}, annote = {Keywords: Prophet Inequalities, Intersection of Matroids} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Benjamin Qi. On Maximizing Sums of Non-Monotone Submodular and Linear Functions. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{qi:LIPIcs.ISAAC.2022.41, author = {Qi, Benjamin}, title = {{On Maximizing Sums of Non-Monotone Submodular and Linear Functions}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.41}, URN = {urn:nbn:de:0030-drops-173263}, doi = {10.4230/LIPIcs.ISAAC.2022.41}, annote = {Keywords: submodular maximization, regularization, continuous greedy, inapproximability} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Moran Feldman and Ariel Szarf. Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{feldman_et_al:LIPIcs.APPROX/RANDOM.2022.33, author = {Feldman, Moran and Szarf, Ariel}, title = {{Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {33:1--33: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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.33}, URN = {urn:nbn:de:0030-drops-171559}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.33}, annote = {Keywords: Maximum matching, semi-streaming algorithms, multi-pass algorithms} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Kobi Bodek and Moran Feldman. Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bodek_et_al:LIPIcs.ESA.2022.23, author = {Bodek, Kobi and Feldman, Moran}, title = {{Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {23:1--23:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.23}, URN = {urn:nbn:de:0030-drops-169618}, doi = {10.4230/LIPIcs.ESA.2022.23}, annote = {Keywords: Unconstrained submodular maximization, regularization, double greedy, non-oblivious local search, inapproximability} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Submodular Maximization Subject to Matroid Intersection on the Fly. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{feldman_et_al:LIPIcs.ESA.2022.52, author = {Feldman, Moran and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico}, title = {{Submodular Maximization Subject to Matroid Intersection on the Fly}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {52:1--52:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.52}, URN = {urn:nbn:de:0030-drops-169902}, doi = {10.4230/LIPIcs.ESA.2022.52}, annote = {Keywords: Submodular Maximization, Matroid Intersection, Streaming Algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. Streaming Submodular Maximization Under Matroid Constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{feldman_et_al:LIPIcs.ICALP.2022.59, author = {Feldman, Moran and Liu, Paul and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico}, title = {{Streaming Submodular Maximization Under Matroid Constraints}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {59:1--59: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.59}, URN = {urn:nbn:de:0030-drops-164007}, doi = {10.4230/LIPIcs.ICALP.2022.59}, annote = {Keywords: Submodular maximization, streaming, matroid, random order} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alaluf_et_al:LIPIcs.ICALP.2020.6, author = {Alaluf, Naor and Ene, Alina and Feldman, Moran and Nguyen, Huy L. and Suh, Andrew}, title = {{Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.6}, URN = {urn:nbn:de:0030-drops-124137}, doi = {10.4230/LIPIcs.ICALP.2020.6}, annote = {Keywords: Submodular maximization, streaming algorithms, cardinality constraint} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{lee_et_al:LIPIcs.ESA.2018.57, author = {Lee, Euiwoong and Singla, Sahil}, title = {{Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {57:1--57:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.57}, URN = {urn:nbn:de:0030-drops-95208}, doi = {10.4230/LIPIcs.ESA.2018.57}, annote = {Keywords: Prophets, Contention Resolution, Stochastic Optimization, Matroids} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Moran Feldman, Moshe Tennenholtz, and Omri Weinstein. Distributed Signaling Games. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{feldman_et_al:LIPIcs.ESA.2016.41, author = {Feldman, Moran and Tennenholtz, Moshe and Weinstein, Omri}, title = {{Distributed Signaling Games}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.41}, URN = {urn:nbn:de:0030-drops-63536}, doi = {10.4230/LIPIcs.ESA.2016.41}, annote = {Keywords: Signaling, display advertising, mechanism design, shapley value} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 160-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{feldman_et_al:LIPIcs.APPROX-RANDOM.2014.160, author = {Feldman, Moran and Izsak, Rani}, title = {{Constrained Monotone Function Maximization and the Supermodular Degree}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {160--175}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.160}, URN = {urn:nbn:de:0030-drops-46950}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.160}, annote = {Keywords: supermodular degree, set function, submodular, matroid, extendible system} }