Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yossi Azar, Shahar Lewkowicz, and Danny Vainstein. List Update with Delays or Time Windows. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{azar_et_al:LIPIcs.ICALP.2024.15, author = {Azar, Yossi and Lewkowicz, Shahar and Vainstein, Danny}, title = {{List Update with Delays or Time Windows}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-201583}, doi = {10.4230/LIPIcs.ICALP.2024.15}, annote = {Keywords: Online, List Update, Delay, Time Window, Deadline} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Nguyễn Kim Thắng. Online Primal-Dual Algorithms with Configuration Linear Programs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{thang:LIPIcs.ISAAC.2020.45, author = {Thắng, Nguy\~{ê}n Kim}, title = {{Online Primal-Dual Algorithms with Configuration Linear Programs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.45}, URN = {urn:nbn:de:0030-drops-133891}, doi = {10.4230/LIPIcs.ISAAC.2020.45}, annote = {Keywords: Configuration Linear Programs, Primal-Dual, Smoothness} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Nguyễn Kim Thắng. An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 84:1-84:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{thang:LIPIcs.MFCS.2020.84, author = {Thắng, Nguy\~{ê}n Kim}, title = {{An Improved Approximation Algorithm for Scheduling Under Arborescence Precedence Constraints}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {84:1--84:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.84}, URN = {urn:nbn:de:0030-drops-127459}, doi = {10.4230/LIPIcs.MFCS.2020.84}, annote = {Keywords: Scheduling, Precedence Constraints, Lagrangian Duality} }
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 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Thắng Nguyễn Kim. A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{nguyenkim:LIPIcs.ISAAC.2019.39, author = {Nguy\~{ê}n Kim, Thắng}, title = {{A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {39:1--39:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.39}, URN = {urn:nbn:de:0030-drops-115351}, doi = {10.4230/LIPIcs.ISAAC.2019.39}, annote = {Keywords: Approximation Algorithms, Congestion Minimization} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Nguyen Kim Thang. Game Efficiency Through Linear Programming Duality. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kimthang:LIPIcs.ITCS.2019.66, author = {Kim Thang, Nguyen}, title = {{Game Efficiency Through Linear Programming Duality}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {66:1--66:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.66}, URN = {urn:nbn:de:0030-drops-101597}, doi = {10.4230/LIPIcs.ITCS.2019.66}, annote = {Keywords: Price of Anarchy, Primal-Dual} }
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 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Nguyen Kim Thang. A Greedy Algorithm for Subspace Approximation Problem. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 30:1-30:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{thang:LIPIcs.SWAT.2018.30, author = {Thang, Nguyen Kim}, title = {{A Greedy Algorithm for Subspace Approximation Problem}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {30:1--30:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.30}, URN = {urn:nbn:de:0030-drops-88562}, doi = {10.4230/LIPIcs.SWAT.2018.30}, annote = {Keywords: Approximation Algorithms, Subspace Approximation} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12, author = {Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel}, title = {{Online Algorithms for Multi-Level Aggregation}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.12}, URN = {urn:nbn:de:0030-drops-63637}, doi = {10.4230/LIPIcs.ESA.2016.12}, annote = {Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Giorgio Lucarelli, Nguyen Kim Thang, Abhinav Srivastav, and Denis Trystram. Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 63:1-63:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{lucarelli_et_al:LIPIcs.ESA.2016.63, author = {Lucarelli, Giorgio and Kim Thang, Nguyen and Srivastav, Abhinav and Trystram, Denis}, title = {{Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {63:1--63:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.63}, URN = {urn:nbn:de:0030-drops-64047}, doi = {10.4230/LIPIcs.ESA.2016.63}, annote = {Keywords: Online algorithms, Non-preemptive scheduling, Resource augmentation, Primal-dual} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Nguyen Kim Thang. Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kimthang:LIPIcs.SWAT.2016.20, author = {Kim Thang, Nguyen}, title = {{Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.20}, URN = {urn:nbn:de:0030-drops-60427}, doi = {10.4230/LIPIcs.SWAT.2016.20}, annote = {Keywords: Online Scheduling, Energy Minimization, Speed Scaling and Power-down, Lagrangian Duality} }