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 264, 38th Computational Complexity Conference (CCC 2023)
Eshan Chattopadhyay and Jyun-Jie Liao. Hardness Against Linear Branching Programs and More. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2023.9, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Hardness Against Linear Branching Programs and More}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {9:1--9:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.9}, URN = {urn:nbn:de:0030-drops-182794}, doi = {10.4230/LIPIcs.CCC.2023.9}, annote = {Keywords: linear branching programs, circuit lower bound, sumset extractors, hitting sets} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 52:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gaitonde_et_al:LIPIcs.ITCS.2023.52, author = {Gaitonde, Jason and Li, Yingkai and Light, Bar and Lucier, Brendan and Slivkins, Aleksandrs}, title = {{Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {52:1--52:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.52}, URN = {urn:nbn:de:0030-drops-175557}, doi = {10.4230/LIPIcs.ITCS.2023.52}, annote = {Keywords: repeated auctions with budgets, pacing, learning in auctions} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
D. Ellis Hershkowitz and Jason Li. O(1) Steiner Point Removal in Series-Parallel Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hershkowitz_et_al:LIPIcs.ESA.2022.66, author = {Hershkowitz, D. Ellis and Li, Jason}, title = {{O(1) Steiner Point Removal in Series-Parallel Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {66:1--66:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.66}, URN = {urn:nbn:de:0030-drops-170041}, doi = {10.4230/LIPIcs.ESA.2022.66}, annote = {Keywords: Metric embeddings, graph algorithms, vertex sparsification} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Zhiyang He, Jason Li, and Magnus Wahlström. Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{he_et_al:LIPIcs.ESA.2021.52, author = {He, Zhiyang and Li, Jason and Wahlstr\"{o}m, Magnus}, title = {{Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {52:1--52:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.52}, URN = {urn:nbn:de:0030-drops-146331}, doi = {10.4230/LIPIcs.ESA.2021.52}, annote = {Keywords: graph theory, vertex sparsifier, representative family, matroid} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2021.23, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Simonov, Kirill}, title = {{On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {23:1--23:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.23}, URN = {urn:nbn:de:0030-drops-140923}, doi = {10.4230/LIPIcs.ICALP.2021.23}, annote = {Keywords: fair clustering, coresets, approximation algorithms} }
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-dev.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 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. FPT Approximation for Constrained Metric k-Median/Means. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goyal_et_al:LIPIcs.IPEC.2020.14, author = {Goyal, Dishant and Jaiswal, Ragesh and Kumar, Amit}, title = {{FPT Approximation for Constrained Metric k-Median/Means}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {14:1--14:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.14}, URN = {urn:nbn:de:0030-drops-133170}, doi = {10.4230/LIPIcs.IPEC.2020.14}, annote = {Keywords: k-means, k-median, approximation algorithms, parameterised algorithms} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Arnold Filtser. Scattering and Sparse Partitions, and Their Applications. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{filtser:LIPIcs.ICALP.2020.47, author = {Filtser, Arnold}, title = {{Scattering and Sparse Partitions, and Their Applications}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {47:1--47:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.47}, URN = {urn:nbn:de:0030-drops-124547}, doi = {10.4230/LIPIcs.ICALP.2020.47}, annote = {Keywords: Scattering partitions, sparse partitions, sparse covers, Steiner point removal, Universal Steiner tree, Universal TSP} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.ICALP.2019.41, author = {Cohen-Addad, Vincent and Li, Jason}, title = {{On the Fixed-Parameter Tractability of Capacitated Clustering}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {41:1--41: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.41}, URN = {urn:nbn:de:0030-drops-106171}, doi = {10.4230/LIPIcs.ICALP.2019.41}, annote = {Keywords: approximation algorithms, fixed-parameter tractability, capacitated, k-median, k-means, clustering, core-sets, Euclidean} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.ICALP.2019.42, author = {Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason}, title = {{Tight FPT Approximations for k-Median and k-Means}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {42:1--42: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.42}, URN = {urn:nbn:de:0030-drops-106182}, doi = {10.4230/LIPIcs.ICALP.2019.42}, annote = {Keywords: approximation algorithms, fixed-parameter tractability, k-median, k-means, clustering, core-sets} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Mohsen Ghaffari and Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ghaffari_et_al:LIPIcs.DISC.2018.31, author = {Ghaffari, Mohsen and Li, Jason}, title = {{New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.31}, URN = {urn:nbn:de:0030-drops-98207}, doi = {10.4230/LIPIcs.DISC.2018.31}, annote = {Keywords: Distributed Graph Algorithms, Mixing Time, Random Graphs, Multi-Commodity Routing} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Bernhard Haeupler and Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{haeupler_et_al:LIPIcs.DISC.2018.33, author = {Haeupler, Bernhard and Li, Jason}, title = {{Faster Distributed Shortest Path Approximations via Shortcuts}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {33:1--33:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.33}, URN = {urn:nbn:de:0030-drops-98229}, doi = {10.4230/LIPIcs.DISC.2018.33}, annote = {Keywords: Distributed Graph Algorithms, Shortest Path, Shortcuts} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Anupam Gupta, Amit Kumar, and Jason Li. Non-Preemptive Flow-Time Minimization via Rejections. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2018.70, author = {Gupta, Anupam and Kumar, Amit and Li, Jason}, title = {{Non-Preemptive Flow-Time Minimization via Rejections}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {70:1--70:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.70}, URN = {urn:nbn:de:0030-drops-90740}, doi = {10.4230/LIPIcs.ICALP.2018.70}, annote = {Keywords: Scheduling, Rejection, Unrelated Machines, Non-Preemptive} }
Feedback for Dagstuhl Publishing