Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147, author = {Loff, Bruno and Skomra, Mateusz}, title = {{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {147:1--147:16}, 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.147}, URN = {urn:nbn:de:0030-drops-202908}, doi = {10.4230/LIPIcs.ICALP.2024.147}, annote = {Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Khaled Elbassioni and Kazuhisa Makino. Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{elbassioni_et_al:LIPIcs.ESA.2019.43, author = {Elbassioni, Khaled and Makino, Kazuhisa}, title = {{Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.43}, URN = {urn:nbn:de:0030-drops-111642}, doi = {10.4230/LIPIcs.ESA.2019.43}, annote = {Keywords: Semidefinite programs, packing and covering, logarithmic potential, primal-dual algorithms, approximate solutions} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Khaled Elbassioni and Kazuhisa Makino. Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{elbassioni_et_al:LIPIcs.SWAT.2018.18, author = {Elbassioni, Khaled and Makino, Kazuhisa}, title = {{Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {18:1--18:14}, 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.18}, URN = {urn:nbn:de:0030-drops-88441}, doi = {10.4230/LIPIcs.SWAT.2018.18}, annote = {Keywords: Totally unimodular matrices, Vertices of polyhedra, Vertex enumeration, Hypergraph transversals, Hypergraph decomposition, Output polynomial-time algorithm} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Khaled Elbassioni. Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{elbassioni:LIPIcs.SoCG.2017.40, author = {Elbassioni, Khaled}, title = {{Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {40:1--40:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.40}, URN = {urn:nbn:de:0030-drops-72289}, doi = {10.4230/LIPIcs.SoCG.2017.40}, annote = {Keywords: VC-dimension, approximation algorithms, fractional covering, multiplicative weights update, art gallery problem, polyhedral separators, geometric cove} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Khaled Elbassioni. Exact Algorithms for List-Coloring of Intersecting Hypergraphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{elbassioni:LIPIcs.IPEC.2016.12, author = {Elbassioni, Khaled}, title = {{Exact Algorithms for List-Coloring of Intersecting Hypergraphs}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.12}, URN = {urn:nbn:de:0030-drops-69444}, doi = {10.4230/LIPIcs.IPEC.2016.12}, annote = {Keywords: Hypergraph coloring, monotone Boolean duality, list coloring, exact algorithms, quasi-polynomial time} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Markov Decision Processes and Stochastic Games with Total Effective Payoff. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 103-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{boros_et_al:LIPIcs.STACS.2015.103, author = {Boros, Endre and Elbassioni, Khaled and Gurvich, Vladimir and Makino, Kazuhisa}, title = {{Markov Decision Processes and Stochastic Games with Total Effective Payoff}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {103--115}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.103}, URN = {urn:nbn:de:0030-drops-49074}, doi = {10.4230/LIPIcs.STACS.2015.103}, annote = {Keywords: Markov decision processes, undiscounted stochastic games, linear programming, mean payoff, total payoff} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 267-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{elbassioni_et_al:LIPIcs.FSTTCS.2012.267, author = {Elbassioni, Khaled and Garg, Naveen and Gupta, Divya and Kumar, Amit and Narula, Vishal and Pal, Arindam}, title = {{Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {267--275}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.267}, URN = {urn:nbn:de:0030-drops-38650}, doi = {10.4230/LIPIcs.FSTTCS.2012.267}, annote = {Keywords: Approximation Algorithms, Integer Decomposition, Linear Programming, Scheduling, Unsplittable Flows} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Katarzyna Paluch, Khaled Elbassioni, and Anke van Zuylen. Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 501-506, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{paluch_et_al:LIPIcs.STACS.2012.501, author = {Paluch, Katarzyna and Elbassioni, Khaled and van Zuylen, Anke}, title = {{Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {501--506}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.501}, URN = {urn:nbn:de:0030-drops-34129}, doi = {10.4230/LIPIcs.STACS.2012.501}, annote = {Keywords: approximation algorithm, maximum asymmetric traveling salesman problem} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julian Mestre, and Domagoj Severdija. Improved Approximations for Guarding 1.5-Dimensional Terrains. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 361-372, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{elbassioni_et_al:LIPIcs.STACS.2009.1841, author = {Elbassioni, Khaled and Krohn, Erik and Matijevic, Domagoj and Mestre, Julian and Severdija, Domagoj}, title = {{Improved Approximations for Guarding 1.5-Dimensional Terrains}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {361--372}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1841}, URN = {urn:nbn:de:0030-drops-18410}, doi = {10.4230/LIPIcs.STACS.2009.1841}, annote = {Keywords: Covering problems, Guarding 1.5-terrains, Approximation algorithms, Linear programming, Totally balanced matrices} }