Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng. Faster Submodular Maximization for Several Classes of Matroids. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 74:1-74:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{henzinger_et_al:LIPIcs.ICALP.2023.74, author = {Henzinger, Monika and Liu, Paul and Vondr\'{a}k, Jan and Zheng, Da Wei}, title = {{Faster Submodular Maximization for Several Classes of Matroids}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {74:1--74:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.74}, URN = {urn:nbn:de:0030-drops-181267}, doi = {10.4230/LIPIcs.ICALP.2023.74}, annote = {Keywords: submodular optimization, dynamic data structures, matching 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 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Linda Cai, Clay Thomas, and S. Matthew Weinberg. Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 61:1-61:32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cai_et_al:LIPIcs.ITCS.2020.61, author = {Cai, Linda and Thomas, Clay and Weinberg, S. Matthew}, title = {{Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {61:1--61:32}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.61}, URN = {urn:nbn:de:0030-drops-117464}, doi = {10.4230/LIPIcs.ITCS.2020.61}, annote = {Keywords: Combinatorial auctions, Posted-Price mechanisms, Submodular valuations, Incentive compatible} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Paul Liu and Jan Vondrak. Submodular Optimization in the MapReduce Model. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 18:1-18:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{liu_et_al:OASIcs.SOSA.2019.18, author = {Liu, Paul and Vondrak, Jan}, title = {{Submodular Optimization in the MapReduce Model}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {18:1--18:10}, 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.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.18}, URN = {urn:nbn:de:0030-drops-100447}, doi = {10.4230/OASIcs.SOSA.2019.18}, annote = {Keywords: mapreduce, submodular, optimization, approximation algorithms} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak. Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 26:1-26:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{chatziafratis_et_al:LIPIcs.ESA.2017.26, author = {Chatziafratis, Vaggos and Roughgarden, Tim and Vondrak, Jan}, title = {{Stability and Recovery for Independence Systems}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {26:1--26:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.26}, URN = {urn:nbn:de:0030-drops-78423}, doi = {10.4230/LIPIcs.ESA.2017.26}, annote = {Keywords: Submodular, approximation, stability, Local Search, Greedy, p-systems} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Tim Roughgarden, Inbal Talgam-Cohen, and Jan Vondrák. When Are Welfare Guarantees Robust?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 22:1-22:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{roughgarden_et_al:LIPIcs.APPROX-RANDOM.2017.22, author = {Roughgarden, Tim and Talgam-Cohen, Inbal and Vondr\'{a}k, Jan}, title = {{When Are Welfare Guarantees Robust?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {22:1--22:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.22}, URN = {urn:nbn:de:0030-drops-75714}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.22}, annote = {Keywords: Valuation (set) functions, gross substitutes, linearity, approximation} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Alina Ene and Jan Vondrák. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 144-159, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{ene_et_al:LIPIcs.APPROX-RANDOM.2014.144, author = {Ene, Alina and Vondr\'{a}k, Jan}, title = {{Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {144--159}, 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.144}, URN = {urn:nbn:de:0030-drops-46943}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.144}, annote = {Keywords: Minimum Cost Submodular Allocation, Submodular Optimization, Hypergraph Labeling} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
T. S. Jayram and Jan Vondrák. Exchangeability and Realizability: De Finetti Theorems on Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 762-778, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{jayram_et_al:LIPIcs.APPROX-RANDOM.2014.762, author = {Jayram, T. S. and Vondr\'{a}k, Jan}, title = {{Exchangeability and Realizability: De Finetti Theorems on Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {762--778}, 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.762}, URN = {urn:nbn:de:0030-drops-47375}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.762}, annote = {Keywords: exchangeability, de Finetti’s Theorem, spectral graph theory, regularity lemma} }
Feedback for Dagstuhl Publishing