Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kobayashi_et_al:LIPIcs.ICALP.2024.100, author = {Kobayashi, Yusuke and Terao, Tatsuya}, title = {{Subquadratic Submodular Maximization with a General Matroid Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {100:1--100:19}, 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.100}, URN = {urn:nbn:de:0030-drops-202437}, doi = {10.4230/LIPIcs.ICALP.2024.100}, annote = {Keywords: submodular maximization, matroid constraint, approximation algorithm, rounding algorithm, query complexity} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof Scheduling with Predictions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{balkanski_et_al:LIPIcs.ITCS.2023.11, author = {Balkanski, Eric and Gkatzelis, Vasilis and Tan, Xizhi}, title = {{Strategyproof Scheduling with Predictions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {11:1--11:22}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.11}, URN = {urn:nbn:de:0030-drops-175143}, doi = {10.4230/LIPIcs.ITCS.2023.11}, annote = {Keywords: Mechanism Design with Predictions, Strategyproof Scheduling} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Aviad Rubinstein and Junyao Zhao. Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 113:1-113:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2022.113, author = {Rubinstein, Aviad and Zhao, Junyao}, title = {{Budget-Smoothed Analysis for Submodular Maximization}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {113:1--113: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.113}, URN = {urn:nbn:de:0030-drops-157095}, doi = {10.4230/LIPIcs.ITCS.2022.113}, annote = {Keywords: Submodular optimization, Beyond worst-case analysis, Greedy algorithms, Hardness of approximation} }