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-dev.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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, and Zhouzi Li. Graph Searching with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{banerjee_et_al:LIPIcs.ITCS.2023.12, author = {Banerjee, Siddhartha and Cohen-Addad, Vincent and Gupta, Anupam and Li, Zhouzi}, title = {{Graph Searching with Predictions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {12:1--12:24}, 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.12}, URN = {urn:nbn:de:0030-drops-175158}, doi = {10.4230/LIPIcs.ITCS.2023.12}, annote = {Keywords: Algorithms with predictions, network algorithms, graph search} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Anupam Gupta. Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gupta:LIPIcs.FSTTCS.2022.1, author = {Gupta, Anupam}, title = {{Algorithms for Uncertain Environments: Going Beyond the Worst-Case}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.1}, URN = {urn:nbn:de:0030-drops-173933}, doi = {10.4230/LIPIcs.FSTTCS.2022.1}, annote = {Keywords: Optimization under Uncertainty, Online Algorithms, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Weina Wang, Anupam Gupta, and Jalani K. Williams. Probing to Minimize. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 120:1-120:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{wang_et_al:LIPIcs.ITCS.2022.120, author = {Wang, Weina and Gupta, Anupam and Williams, Jalani K.}, title = {{Probing to Minimize}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {120:1--120:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.120}, URN = {urn:nbn:de:0030-drops-157169}, doi = {10.4230/LIPIcs.ITCS.2022.120}, annote = {Keywords: approximation algorithms, stochastic probing, minimization} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Anupam Gupta, Amit Kumar, and Sahil Singla. Bag-Of-Tasks Scheduling on Related Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2021.3, author = {Gupta, Anupam and Kumar, Amit and Singla, Sahil}, title = {{Bag-Of-Tasks Scheduling on Related Machines}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {3:1--3:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.3}, URN = {urn:nbn:de:0030-drops-146967}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.3}, annote = {Keywords: approximation algorithms, scheduling, bag-of-tasks, related machines} }
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-dev.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 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Anupam Gupta, Benjamin Moseley, and Rudy Zhou. Structural Iterative Rounding for Generalized k-Median Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 77:1-77:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2021.77, author = {Gupta, Anupam and Moseley, Benjamin and Zhou, Rudy}, title = {{Structural Iterative Rounding for Generalized k-Median Problems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {77:1--77:18}, 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.77}, URN = {urn:nbn:de:0030-drops-141465}, doi = {10.4230/LIPIcs.ICALP.2021.77}, annote = {Keywords: approximation algorithms, clustering, linear programming} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. Online Carpooling Using Expander Decompositions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2020.23, author = {Gupta, Anupam and Krishnaswamy, Ravishankar and Kumar, Amit and Singla, Sahil}, title = {{Online Carpooling Using Expander Decompositions}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {23:1--23:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.23}, URN = {urn:nbn:de:0030-drops-132647}, doi = {10.4230/LIPIcs.FSTTCS.2020.23}, annote = {Keywords: Online Algorithms, Discrepancy Minimization, Carpooling} }
Published in: LIPIcs, Volume 156, 1st Symposium on Foundations of Responsible Computing (FORC 2020)
Christopher Jung, Sampath Kannan, and Neil Lutz. Service in Your Neighborhood: Fairness in Center Location. In 1st Symposium on Foundations of Responsible Computing (FORC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 156, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jung_et_al:LIPIcs.FORC.2020.5, author = {Jung, Christopher and Kannan, Sampath and Lutz, Neil}, title = {{Service in Your Neighborhood: Fairness in Center Location}}, booktitle = {1st Symposium on Foundations of Responsible Computing (FORC 2020)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-142-9}, ISSN = {1868-8969}, year = {2020}, volume = {156}, editor = {Roth, Aaron}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2020.5}, URN = {urn:nbn:de:0030-drops-120215}, doi = {10.4230/LIPIcs.FORC.2020.5}, annote = {Keywords: Fairness, Clustering, Facility Location} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Domagoj Bradac, Anupam Gupta, Sahil Singla, and Goran Zuzic. Robust Algorithms for the Secretary Problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 32:1-32:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bradac_et_al:LIPIcs.ITCS.2020.32, author = {Bradac, Domagoj and Gupta, Anupam and Singla, Sahil and Zuzic, Goran}, title = {{Robust Algorithms for the Secretary Problem}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {32:1--32:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.32}, URN = {urn:nbn:de:0030-drops-117171}, doi = {10.4230/LIPIcs.ITCS.2020.32}, annote = {Keywords: stochastic optimization, robust optimization, secretary problem, matroid secretary, robust secretary} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Domagoj Bradac, Sahil Singla, and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bradac_et_al:LIPIcs.APPROX-RANDOM.2019.49, author = {Bradac, Domagoj and Singla, Sahil and Zuzic, Goran}, title = {{(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {49:1--49:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.49}, URN = {urn:nbn:de:0030-drops-112641}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.49}, annote = {Keywords: stochastic programming, adaptivity gaps, stochastic multi-value probing, submodular functions, k-extendible systems, adaptive strategy, matroid intersection} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Yair Bartal, Nova Fandina, and Ofer Neiman. Covering Metric Spaces by Few Trees. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bartal_et_al:LIPIcs.ICALP.2019.20, author = {Bartal, Yair and Fandina, Nova and Neiman, Ofer}, title = {{Covering Metric Spaces by Few Trees}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {20:1--20:16}, 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.20}, URN = {urn:nbn:de:0030-drops-105967}, doi = {10.4230/LIPIcs.ICALP.2019.20}, annote = {Keywords: tree cover, Ramsey tree cover, probabilistic hierarchical family} }
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 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla. Non-Clairvoyant Precedence Constrained Scheduling. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{garg_et_al:LIPIcs.ICALP.2019.63, author = {Garg, Naveen and Gupta, Anupam and Kumar, Amit and Singla, Sahil}, title = {{Non-Clairvoyant Precedence Constrained Scheduling}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {63:1--63: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.63}, URN = {urn:nbn:de:0030-drops-106394}, doi = {10.4230/LIPIcs.ICALP.2019.63}, annote = {Keywords: Online algorithms, Scheduling, Primal-Dual analysis, Nash welfare} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic Online Metric Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2019.67, author = {Gupta, Anupam and Guruganesh, Guru and Peng, Binghui and Wajc, David}, title = {{Stochastic Online Metric Matching}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {67:1--67: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.67}, URN = {urn:nbn:de:0030-drops-106430}, doi = {10.4230/LIPIcs.ICALP.2019.67}, annote = {Keywords: stochastic, online, online matching, metric matching} }
Feedback for Dagstuhl Publishing