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 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering on Sliding Windows in Polylogarithmic Space. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 350-364, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{braverman_et_al:LIPIcs.FSTTCS.2015.350, author = {Braverman, Vladimir and Lang, Harry and Levin, Keith and Monemizadeh, Morteza}, title = {{Clustering on Sliding Windows in Polylogarithmic Space}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {350--364}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.350}, URN = {urn:nbn:de:0030-drops-56549}, doi = {10.4230/LIPIcs.FSTTCS.2015.350}, annote = {Keywords: Streaming, Clustering, Sliding windows} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Markus Chimani and Joachim Spoerhase. Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 238-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chimani_et_al:LIPIcs.STACS.2015.238, author = {Chimani, Markus and Spoerhase, Joachim}, title = {{Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {238--248}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.238}, URN = {urn:nbn:de:0030-drops-49170}, doi = {10.4230/LIPIcs.STACS.2015.238}, annote = {Keywords: network design, approximation algorithm, shallow-light spanning trees, spanners} }
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} }
Feedback for Dagstuhl Publishing