Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Chandra Chekuri and Kent Quanrud. Independent Sets in Elimination Graphs with a Submodular Objective. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2023.24, author = {Chekuri, Chandra and Quanrud, Kent}, title = {{Independent Sets in Elimination Graphs with a Submodular Objective}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {24:1--24:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.24}, URN = {urn:nbn:de:0030-drops-188490}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.24}, annote = {Keywords: elimination graphs, independent set, submodular maximization, primal-dual} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{harb_et_al:LIPIcs.ESA.2023.56, author = {Harb, Elfarouk and Quanrud, Kent and Chekuri, Chandra}, title = {{Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.56}, URN = {urn:nbn:de:0030-drops-187091}, doi = {10.4230/LIPIcs.ESA.2023.56}, annote = {Keywords: Polymatroid, lexicographically optimum base, densest subgraph, tree packing} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{morgan_et_al:LIPIcs.DISC.2021.33, author = {Morgan, Adir and Solomon, Shay and Wein, Nicole}, title = {{Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {33:1--33:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.33}, URN = {urn:nbn:de:0030-drops-148353}, doi = {10.4230/LIPIcs.DISC.2021.33}, annote = {Keywords: Graph Algorithms, Dominating Set, Bounded Arboricity, Linear time algorithms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Elena Grigorescu, Young-San Lin, and Kent Quanrud. Online Directed Spanners and Steiner Forests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 5:1-5:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grigorescu_et_al:LIPIcs.APPROX/RANDOM.2021.5, author = {Grigorescu, Elena and Lin, Young-San and Quanrud, Kent}, title = {{Online Directed Spanners and Steiner Forests}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {5:1--5:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.5}, URN = {urn:nbn:de:0030-drops-146987}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.5}, annote = {Keywords: online directed pairwise spanners, online directed Steiner forests, online covering/packing linear programming, primal-dual approach} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2021.24, author = {Chekuri, Chandra and Quanrud, Kent and Torres, Manuel R.}, title = {{Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {24:1--24:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.24}, URN = {urn:nbn:de:0030-drops-147177}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.24}, annote = {Keywords: bounded degree spanning tree, crossing spanning tree, swap rounding, fast approximation algorithms} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Chandra Chekuri and Kent Quanrud. Faster Algorithms for Rooted Connectivity in Directed Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2021.49, author = {Chekuri, Chandra and Quanrud, Kent}, title = {{Faster Algorithms for Rooted Connectivity in Directed Graphs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {49:1--49:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.49}, URN = {urn:nbn:de:0030-drops-141187}, doi = {10.4230/LIPIcs.ICALP.2021.49}, annote = {Keywords: rooted connectivity, directed graph, fast algorithm, sparsification} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Chandra Chekuri and Kent Quanrud. Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2021.50, author = {Chekuri, Chandra and Quanrud, Kent}, title = {{Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {50:1--50:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.50}, URN = {urn:nbn:de:0030-drops-141199}, doi = {10.4230/LIPIcs.ICALP.2021.50}, annote = {Keywords: cuts, vertex connectivity, hypergraphs, fast algorithms, submodularity, bisumodularity, lattices, isolating cuts, element connectivity} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Kent Quanrud. Fast and Deterministic Approximations for k-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{quanrud:LIPIcs.APPROX-RANDOM.2019.23, author = {Quanrud, Kent}, title = {{Fast and Deterministic Approximations for k-Cut}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.23}, URN = {urn:nbn:de:0030-drops-112388}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.23}, annote = {Keywords: k-cut, multiplicative weight updates} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Kent Quanrud. Approximating Optimal Transport With Linear Programs. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 6:1-6:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{quanrud:OASIcs.SOSA.2019.6, author = {Quanrud, Kent}, title = {{Approximating Optimal Transport With Linear Programs}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {6:1--6:9}, 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.6}, URN = {urn:nbn:de:0030-drops-100321}, doi = {10.4230/OASIcs.SOSA.2019.6}, annote = {Keywords: optimal transport, fast approximations, linear programming} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Chandra Chekuri, Kent Quanrud, and Chao Xu. LP Relaxation and Tree Packing for Minimum k-cuts. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chekuri_et_al:OASIcs.SOSA.2019.7, author = {Chekuri, Chandra and Quanrud, Kent and Xu, Chao}, title = {{LP Relaxation and Tree Packing for Minimum k-cuts}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {7:1--7:18}, 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.7}, URN = {urn:nbn:de:0030-drops-100335}, doi = {10.4230/OASIcs.SOSA.2019.7}, annote = {Keywords: k-cut, LP relaxation, tree packing} }
Feedback for Dagstuhl Publishing