Published in: Dagstuhl Reports, Volume 13, Issue 10 (2024)
Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak. Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422). In Dagstuhl Reports, Volume 13, Issue 10, pp. 76-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{li_et_al:DagRep.13.10.76, author = {Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol}, title = {{Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422)}}, pages = {76--89}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {13}, number = {10}, editor = {Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.10.76}, URN = {urn:nbn:de:0030-drops-198357}, doi = {10.4230/DagRep.13.10.76}, annote = {Keywords: approximation, graph algorithm, maximum flow, minimum cut, network design} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Efficient Algorithms and Hardness Results for the Weighted k-Server Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2023.12, author = {Gupta, Anupam and Kumar, Amit and Panigrahi, Debmalya}, title = {{Efficient Algorithms and Hardness Results for the Weighted k-Server Problem}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {12:1--12:19}, 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.12}, URN = {urn:nbn:de:0030-drops-188375}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.12}, annote = {Keywords: Online Algorithms, Weighted k-server, Integrality Gap, Hardness} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2023.43, author = {Cohen, Ilan Reuven and Panigrahi, Debmalya}, title = {{A General Framework for Learning-Augmented Online Allocation}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {43:1--43:21}, 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.43}, URN = {urn:nbn:de:0030-drops-180952}, doi = {10.4230/LIPIcs.ICALP.2023.43}, annote = {Keywords: Algorithms with predictions, Scheduling algorithms, Online algorithms} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, and Neal E. Young. Online Paging with Heterogeneous Cache Slots. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chrobak_et_al:LIPIcs.STACS.2023.23, author = {Chrobak, Marek and Haney, Samuel and Liaee, Mehraneh and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi and Young, Neal E.}, title = {{Online Paging with Heterogeneous Cache Slots}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {23:1--23:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.23}, URN = {urn:nbn:de:0030-drops-176759}, doi = {10.4230/LIPIcs.STACS.2023.23}, annote = {Keywords: Caching and paging algorithms, k-server, weighted paging, laminar family} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Simon Apers and Troy Lee. Quantum Complexity of Minimum Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 28:1-28:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{apers_et_al:LIPIcs.CCC.2021.28, author = {Apers, Simon and Lee, Troy}, title = {{Quantum Complexity of Minimum Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {28:1--28:33}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.28}, URN = {urn:nbn:de:0030-drops-143026}, doi = {10.4230/LIPIcs.CCC.2021.28}, annote = {Keywords: Quantum algorithms, quantum query complexity, minimum cut} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of Directed Graphs via Cut Balance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cen_et_al:LIPIcs.ICALP.2021.45, author = {Cen, Ruoxu and Cheng, Yu and Panigrahi, Debmalya and Sun, Kevin}, title = {{Sparsification of Directed Graphs via Cut Balance}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {45:1--45:21}, 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.45}, URN = {urn:nbn:de:0030-drops-141143}, doi = {10.4230/LIPIcs.ICALP.2021.45}, annote = {Keywords: Graph sparsification, directed graphs, cut sketches, space complexity} }
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 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Universal Algorithms for Clustering Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ganesh_et_al:LIPIcs.ICALP.2021.70, author = {Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya}, title = {{Universal Algorithms for Clustering Problems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {70:1--70: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.70}, URN = {urn:nbn:de:0030-drops-141397}, doi = {10.4230/LIPIcs.ICALP.2021.70}, annote = {Keywords: universal algorithms, clustering, k-median, k-means, k-center} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Ilan Cohen, Sungjin Im, and Debmalya Panigrahi. Online Two-Dimensional Load Balancing. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2020.34, author = {Cohen, Ilan and Im, Sungjin and Panigrahi, Debmalya}, title = {{Online Two-Dimensional Load Balancing}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {34:1--34:21}, 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.34}, URN = {urn:nbn:de:0030-drops-124415}, doi = {10.4230/LIPIcs.ICALP.2020.34}, annote = {Keywords: Online algorithms, scheduling, multi-dimensional} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Robust Algorithms for TSP and Steiner Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ganesh_et_al:LIPIcs.ICALP.2020.54, author = {Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya}, title = {{Robust Algorithms for TSP and Steiner Tree}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {54:1--54:18}, 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.54}, URN = {urn:nbn:de:0030-drops-124619}, doi = {10.4230/LIPIcs.ICALP.2020.54}, annote = {Keywords: Robust optimization, Steiner tree, traveling salesman problem} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online Algorithms for Weighted Paging with Predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 69:1-69:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jiang_et_al:LIPIcs.ICALP.2020.69, author = {Jiang, Zhihao and Panigrahi, Debmalya and Sun, Kevin}, title = {{Online Algorithms for Weighted Paging with Predictions}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {69:1--69:18}, 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.69}, URN = {urn:nbn:de:0030-drops-124761}, doi = {10.4230/LIPIcs.ICALP.2020.69}, annote = {Keywords: Online algorithms, paging} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Retracting Graphs to Cycles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haney_et_al:LIPIcs.ICALP.2019.70, author = {Haney, Samuel and Liaee, Mehraneh and Maggs, Bruce M. and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi}, title = {{Retracting Graphs to Cycles}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {70:1--70:15}, 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.70}, URN = {urn:nbn:de:0030-drops-106462}, doi = {10.4230/LIPIcs.ICALP.2019.70}, annote = {Keywords: Graph algorithms, Graph embedding, Planar graphs, Approximation algorithms} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Hsien-Chih Chang, and Allen Xiao. Efficient Algorithms for Geometric Partial Matching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.6, author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Xiao, Allen}, title = {{Efficient Algorithms for Geometric Partial Matching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.6}, URN = {urn:nbn:de:0030-drops-104109}, doi = {10.4230/LIPIcs.SoCG.2019.6}, annote = {Keywords: partial matching, transportation, optimal transport, minimum-cost flow, bichromatic closest pair} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, and Venetia Pliatsika. Profit Sharing and Efficiency in Utility Games. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gollapudi_et_al:LIPIcs.ESA.2017.43, author = {Gollapudi, Sreenivas and Kollias, Kostas and Panigrahi, Debmalya and Pliatsika, Venetia}, title = {{Profit Sharing and Efficiency in Utility Games}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {43:1--43:14}, 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.43}, URN = {urn:nbn:de:0030-drops-78329}, doi = {10.4230/LIPIcs.ESA.2017.43}, annote = {Keywords: Price of anarchy, submodular maximization, coverage functions} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Symmetric Interdiction for Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{haney_et_al:LIPIcs.APPROX-RANDOM.2017.9, author = {Haney, Samuel and Maggs, Bruce and Maiti, Biswaroop and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi}, title = {{Symmetric Interdiction for Matching Problems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {9:1--9:19}, 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.9}, URN = {urn:nbn:de:0030-drops-75587}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.9}, annote = {Keywords: Approximation algorithms, matching, interdiction Digital Object} }
Feedback for Dagstuhl Publishing