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} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Alina Ene, Viswanath Nagarajan, and Rishi Saket. Approximation Algorithms for Stochastic k-TSP. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 27:1-27:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{ene_et_al:LIPIcs.FSTTCS.2017.27, author = {Ene, Alina and Nagarajan, Viswanath and Saket, Rishi}, title = {{Approximation Algorithms for Stochastic k-TSP}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.27}, URN = {urn:nbn:de:0030-drops-83910}, doi = {10.4230/LIPIcs.FSTTCS.2017.27}, annote = {Keywords: Stochastic TSP, algorithms, approximation, adaptivity gap} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Chandra Chekuri, Alina Ene, and Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 7:1-7:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2016.7, author = {Chekuri, Chandra and Ene, Alina and Pilipczuk, Marcin}, title = {{Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.7}, URN = {urn:nbn:de:0030-drops-62737}, doi = {10.4230/LIPIcs.ICALP.2016.7}, annote = {Keywords: Disjoint paths, symmetric demands, planar directed graph} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On Routing Disjoint Paths in Bounded Treewidth Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 15:1-15:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{ene_et_al:LIPIcs.SWAT.2016.15, author = {Ene, Alina and Mnich, Matthias and Pilipczuk, Marcin and Risteski, Andrej}, title = {{On Routing Disjoint Paths in Bounded Treewidth Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.15}, URN = {urn:nbn:de:0030-drops-60378}, doi = {10.4230/LIPIcs.SWAT.2016.15}, annote = {Keywords: Algorithms and data structures, disjoint paths, treewidth} }
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} }
Feedback for Dagstuhl Publishing