Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kent Quanrud. Adaptive Sparsification for Matroid Intersection. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{quanrud:LIPIcs.ICALP.2024.118, author = {Quanrud, Kent}, title = {{Adaptive Sparsification for Matroid Intersection}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {118:1--118: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.118}, URN = {urn:nbn:de:0030-drops-202614}, doi = {10.4230/LIPIcs.ICALP.2024.118}, annote = {Keywords: Matroid intersection, adaptive sparsification, multiplicative-weight udpates, primal-dual} }
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 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 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alina Ene and Huy L. Nguyen. A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ene_et_al:LIPIcs.ICALP.2019.53, author = {Ene, Alina and Nguyen, Huy L.}, title = {{A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {53:1--53:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.53}, URN = {urn:nbn:de:0030-drops-106290}, doi = {10.4230/LIPIcs.ICALP.2019.53}, annote = {Keywords: submodular maximization, knapsack constraint, fast algorithms} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alina Ene and Huy L. Nguyen. Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ene_et_al:LIPIcs.ICALP.2019.54, author = {Ene, Alina and Nguyen, Huy L.}, title = {{Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {54:1--54: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.54}, URN = {urn:nbn:de:0030-drops-106303}, doi = {10.4230/LIPIcs.ICALP.2019.54}, annote = {Keywords: submodular maximization, matroid constraints, fast running times} }