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: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, and Kamesh Munagala. Online Learning and Bandits with Queried Hints. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bhaskara_et_al:LIPIcs.ITCS.2023.16, author = {Bhaskara, Aditya and Gollapudi, Sreenivas and Im, Sungjin and Kollias, Kostas and Munagala, Kamesh}, title = {{Online Learning and Bandits with Queried Hints}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {16:1--16: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.16}, URN = {urn:nbn:de:0030-drops-175197}, doi = {10.4230/LIPIcs.ITCS.2023.16}, annote = {Keywords: Online learning, multi-armed bandits, regret} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, and Joshua R. Wang. Caching with Reserves. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ibrahimpur_et_al:LIPIcs.APPROX/RANDOM.2022.52, author = {Ibrahimpur, Sharat and Purohit, Manish and Svitkina, Zoya and Vee, Erik and Wang, Joshua R.}, title = {{Caching with Reserves}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {52:1--52:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, 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.2022.52}, URN = {urn:nbn:de:0030-drops-171741}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.52}, annote = {Keywords: Approximation Algorithms, Online Algorithms, Caching} }
Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)
Hung Q. Ngo. On an Information Theoretic Approach to Cardinality Estimation (Invited Talk). In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ngo:LIPIcs.ICDT.2022.1, author = {Ngo, Hung Q.}, title = {{On an Information Theoretic Approach to Cardinality Estimation}}, booktitle = {25th International Conference on Database Theory (ICDT 2022)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-223-5}, ISSN = {1868-8969}, year = {2022}, volume = {220}, editor = {Olteanu, Dan and Vortmeier, Nils}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.1}, URN = {urn:nbn:de:0030-drops-158750}, doi = {10.4230/LIPIcs.ICDT.2022.1}, annote = {Keywords: Cardinality Estimation, Information Theory, Polymatroid Bound, Worst-case Optimal Join} }
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-dev.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 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-dev.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 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-dev.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 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-dev.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} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, and Kamesh Munagala. A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{im_et_al:LIPIcs.APPROX-RANDOM.2016.10, author = {Im, Sungjin and Kulkarni, Janardhan and Moseley, Benjamin and Munagala, Kamesh}, title = {{A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, 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.2016.10}, URN = {urn:nbn:de:0030-drops-66336}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.10}, annote = {Keywords: Polytope constraints, average flow time, multi-clusters, online scheduling, and competitive analysis} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive Analysis of Constrained Queueing Systems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 143:1-143:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{im_et_al:LIPIcs.ICALP.2016.143, author = {Im, Sungjin and Kulkarni, Janardhan and Munagala, Kamesh}, title = {{Competitive Analysis of Constrained Queueing Systems}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {143:1--143:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.143}, URN = {urn:nbn:de:0030-drops-62876}, doi = {10.4230/LIPIcs.ICALP.2016.143}, annote = {Keywords: Online scheduling, Average flow time, Switch network, Adversarial} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Stochastic Scheduling of Heavy-tailed Jobs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 474-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{im_et_al:LIPIcs.STACS.2015.474, author = {Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk}, title = {{Stochastic Scheduling of Heavy-tailed Jobs}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {474--486}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.474}, URN = {urn:nbn:de:0030-drops-49359}, doi = {10.4230/LIPIcs.STACS.2015.474}, annote = {Keywords: stochastic scheduling, completion time, approximation} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Sungjin Im, Maxim Sviridenko, and Ruben van der Zwaan. Preemptive and Non-Preemptive Generalized Min Sum Set Cover. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{im_et_al:LIPIcs.STACS.2012.465, author = {Im, Sungjin and Sviridenko, Maxim and van der Zwaan, Ruben}, title = {{Preemptive and Non-Preemptive Generalized Min Sum Set Cover}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {465--476}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.465}, URN = {urn:nbn:de:0030-drops-33991}, doi = {10.4230/LIPIcs.STACS.2012.465}, annote = {Keywords: Set Cover, Approximation, Preemption, Latency, Average cover time} }
Feedback for Dagstuhl Publishing