Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Benjamin Moseley, Heather Newman, and Kirk Pruhs. Online k-Median with Consistent Clusters. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{moseley_et_al:LIPIcs.APPROX/RANDOM.2024.20, author = {Moseley, Benjamin and Newman, Heather and Pruhs, Kirk}, title = {{Online k-Median with Consistent Clusters}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {20:1--20:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.20}, URN = {urn:nbn:de:0030-drops-210133}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.20}, annote = {Keywords: k-median, online algorithms, learning-augmented algorithms, beyond worst-case analysis} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sami Davies, Benjamin Moseley, and Heather Newman. Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{davies_et_al:LIPIcs.ICALP.2024.52, author = {Davies, Sami and Moseley, Benjamin and Newman, Heather}, title = {{Simultaneously Approximating All 𝓁\underlinep-Norms in Correlation Clustering}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {52:1--52:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.52}, URN = {urn:nbn:de:0030-drops-201950}, doi = {10.4230/LIPIcs.ICALP.2024.52}, annote = {Keywords: Approximation algorithms, correlation clustering, all-norms, lp-norms} }
Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)
Sungjin Im, Benjamin Moseley, Hung Ngo, and Kirk Pruhs. On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{im_et_al:LIPIcs.ICDT.2024.11, author = {Im, Sungjin and Moseley, Benjamin and Ngo, Hung and Pruhs, Kirk}, title = {{On the Convergence Rate of Linear Datalog ^∘ over Stable Semirings}}, booktitle = {27th International Conference on Database Theory (ICDT 2024)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-312-6}, ISSN = {1868-8969}, year = {2024}, volume = {290}, editor = {Cormode, Graham and Shekelyan, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.11}, URN = {urn:nbn:de:0030-drops-197939}, doi = {10.4230/LIPIcs.ICDT.2024.11}, annote = {Keywords: Datalog, convergence rate, semiring} }
Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)
Nicole Megow, Benjamin J. Moseley, David Shmoys, Ola Svensson, Sergei Vassilvitskii, and Jens Schlöter. Scheduling (Dagstuhl Seminar 23061). In Dagstuhl Reports, Volume 13, Issue 2, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{megow_et_al:DagRep.13.2.1, author = {Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens}, title = {{Scheduling (Dagstuhl Seminar 23061)}}, pages = {1--19}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {2}, editor = {Megow, Nicole and Moseley, Benjamin J. and Shmoys, David and Svensson, Ola and Vassilvitskii, Sergei and Schl\"{o}ter, Jens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.1}, URN = {urn:nbn:de:0030-drops-191789}, doi = {10.4230/DagRep.13.2.1}, annote = {Keywords: scheduling, mathematical optimization, approximation algorithms, learning methods, uncertainty} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lavastida_et_al:LIPIcs.ESA.2021.59, author = {Lavastida, Thomas and Moseley, Benjamin and Ravi, R. and Xu, Chenyang}, title = {{Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {59:1--59:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.59}, URN = {urn:nbn:de:0030-drops-146405}, doi = {10.4230/LIPIcs.ESA.2021.59}, annote = {Keywords: Learning-augmented algorithms, Online algorithms, Flow allocation} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Marilena Leichter, Benjamin Moseley, and Kirk Pruhs. An Efficient Reduction of a Gammoid to a Partition Matroid. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{leichter_et_al:LIPIcs.ESA.2021.62, author = {Leichter, Marilena and Moseley, Benjamin and Pruhs, Kirk}, title = {{An Efficient Reduction of a Gammoid to a Partition Matroid}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {62:1--62:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.62}, URN = {urn:nbn:de:0030-drops-146432}, doi = {10.4230/LIPIcs.ESA.2021.62}, annote = {Keywords: Matroid, Gammoid, Reduction, Algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Mahmoud Abo-Khamis, Ryan Curtin, Sungjin Im, Benjamin Moseley, Hung Ngo, Kirk Pruhs, and Alireza Samadian. An Approximation Algorithm for the Matrix Tree Multiplication Problem. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abokhamis_et_al:LIPIcs.MFCS.2021.6, author = {Abo-Khamis, Mahmoud and Curtin, Ryan and Im, Sungjin and Moseley, Benjamin and Ngo, Hung and Pruhs, Kirk and Samadian, Alireza}, title = {{An Approximation Algorithm for the Matrix Tree Multiplication Problem}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.6}, URN = {urn:nbn:de:0030-drops-144464}, doi = {10.4230/LIPIcs.MFCS.2021.6}, annote = {Keywords: Matrix Multiplication, Approximation Algorithm} }
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.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 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Benjamin Moseley, Kirk Pruhs, Alireza Samadian, and Yuyan Wang. Relational Algorithms for k-Means Clustering. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 97:1-97:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{moseley_et_al:LIPIcs.ICALP.2021.97, author = {Moseley, Benjamin and Pruhs, Kirk and Samadian, Alireza and Wang, Yuyan}, title = {{Relational Algorithms for k-Means Clustering}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {97:1--97: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.97}, URN = {urn:nbn:de:0030-drops-141668}, doi = {10.4230/LIPIcs.ICALP.2021.97}, annote = {Keywords: k-means, clustering, approximation, big-data, databases} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lucarelli_et_al:LIPIcs.FSTTCS.2019.24, author = {Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis}, title = {{Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {24:1--24:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.24}, URN = {urn:nbn:de:0030-drops-115867}, doi = {10.4230/LIPIcs.FSTTCS.2019.24}, annote = {Keywords: Online Algorithms, Scheduling, Resource Augmentation} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Benjamin Moseley and Maxim Sviridenko. Submodular Optimization with Contention Resolution Extensions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{moseley_et_al:LIPIcs.APPROX-RANDOM.2019.3, author = {Moseley, Benjamin and Sviridenko, Maxim}, title = {{Submodular Optimization with Contention Resolution Extensions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {3:1--3:17}, 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.3}, URN = {urn:nbn:de:0030-drops-112188}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.3}, annote = {Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Benjamin Moseley. Scheduling to Approximate Minimization Objectives on Identical Machines. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 86:1-86:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{moseley:LIPIcs.ICALP.2019.86, author = {Moseley, Benjamin}, title = {{Scheduling to Approximate Minimization Objectives on Identical Machines}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {86:1--86: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.86}, URN = {urn:nbn:de:0030-drops-106621}, doi = {10.4230/LIPIcs.ICALP.2019.86}, annote = {Keywords: Scheduling, LP rounding, Approximation Algorithms} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Manish Purohit. Matroid Coflow Scheduling. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{im_et_al:LIPIcs.ICALP.2019.145, author = {Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk and Purohit, Manish}, title = {{Matroid Coflow Scheduling}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {145:1--145:13}, 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.145}, URN = {urn:nbn:de:0030-drops-107213}, doi = {10.4230/LIPIcs.ICALP.2019.145}, annote = {Keywords: Coflow Scheduling, Concurrent Open Shop, Matroid Scheduling} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Giorgio Lucarelli, Benjamin Moseley, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{lucarelli_et_al:LIPIcs.ESA.2018.59, author = {Lucarelli, Giorgio and Moseley, Benjamin and Thang, Nguyen Kim and Srivastav, Abhinav and Trystram, Denis}, title = {{Online Non-Preemptive Scheduling to Minimize Weighted Flow-time on Unrelated Machines}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {59:1--59:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah 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.2018.59}, URN = {urn:nbn:de:0030-drops-95226}, doi = {10.4230/LIPIcs.ESA.2018.59}, annote = {Keywords: Online Algorithms, Scheduling, Resource Augmentation} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Clifford Stein. Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 51:1-51:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{im_et_al:LIPIcs.ESA.2017.51, author = {Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk and Stein, Clifford}, title = {{Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {51:1--51:10}, 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.51}, URN = {urn:nbn:de:0030-drops-78287}, doi = {10.4230/LIPIcs.ESA.2017.51}, annote = {Keywords: Posted pricing scheme, online scheduling, related machines, maximum flow time, competitiveness analysis} }
Feedback for Dagstuhl Publishing