Hung Hoang

About

I'm a postdoctoral researcher in the Algorithms and Complexity Group at TU Wien under the mentorship of Robert Ganian since Nov 2023. Before that, I worked at Amazon for a year as an applied scientist, where I built and analysed optimisation models for the transportation network of the company.

In 2022, I finished my doctorate at ETH Zurich, in the Theory of Combinatorial Algorithm Group of Bernd Gärtner and Emo Welzl. My supervisor was Bernd Gärtner. Before, I studied a master's programme in operational research at London School of Economics, where I wrote a thesis under the supervision of Gregory Sorkin.

My general research interests are algorithms, computational complexity, discrete mathematics, combinatorics, and optimisation. In particular, I am interested in algorithmic questions in many areas such as combinatorial optimisation, graph theory, operational research, and computational geometry.

Contact

E-mail: phuchung.hoang{at}gmail

Preprints

Parameterized Complexity of Efficient Sortation [arxiv]
(with Robert Ganian and Simon Wietheger)

Generating all invertible matrices by row operations [arxiv]
(with Petr Gregor, Arturo Merino, and Ondřej Mička, )

Publications - Journals

Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs [arxiv]
(with Sriram Bhyravarapu, Tim A. Hartmann, Subrahmanyam Kalyanasundaram, and I. Vinod Reddy)
in Algorithmica, 2024

Assistance and Interdiction Problems on Interval Graphs [arxiv]
(with Stefan Lendl and Lasse Wulf)
in Discrete Applied Mathematics, 340:153-170, 2023

Combinatorial generation via permutation languages. V. Acyclic orientations [arxiv]
(with Jean Cardinal, Arturo Merino, Ondřej Mička, and Torsten Mütze)
in SIAM Journal on Discrete Mathematics, 37(3), 2023

On approximating the rank of graph divisors
(with Kristóf Bérczi and Lilla Tóthmérész)
in Discrete Mathematics, 346(9), 2023

Combinatorial generation via permutation languages: I. Fundamentals [arxiv]
(with Elizabeth Hartung, Torsten Mütze, and Aaron Williams)
in Transactions of the AMS, 375:2255-2291, 2022

Combinatorial generation via permutation languages: II. Lattice congruences [arxiv]
(with Torsten Mütze)
in Israel Journal of Mathematics, 244:359–417, 2021

Publications - Conference Proceedings

The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5 [arxiv]
(with Sophia Heimann and Stefan Hougardy)
in Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), to appear

Drawings of Complete Multipartite Graphs Up to Triangle Flips
(with Oswin Aichholzer, Man-Kwun Chiu, Michael Hoffmann, Jan Kynčl, Yannic Maus, Birgit Vogtenhuber, Alexandra Weinberger )
in Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)

Zigzagging through acyclic orientations of graphs and hypergraphs
(with Jean Cardinal, Arturo Merino, Ondřej Mička, and Torsten Mütze)
in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA23)

A Subexponential Algorithm for ARRIVAL
(with Bernd Gärtner and Sebastian Haslebacher)
in Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Combinatorial generation via permutation languages [poster]
(with Elizabeth Hartung, Torsten Mütze, and Aaron Williams)
in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA20)

Manuscripts

On the PLS-completeness of TSP/k-Opt
(with Stefan Hougardy)
Technical report at University of Bonn

On Two Combinatorial Reconfiguration Problems: Reachability and Hamiltonicity
Doctoral thesis at ETH Zürich

Teaching

Efficient Algorithms, TU Wien, Winter 2023

Optimization in Data Science, ETH Zurich, Spring 2022

Algorithms Lab, ETH Zurich, Autumn 2021

Computer Science 1, ETH Zurich, Spring 2021

Algorithms Lab, ETH Zurich, Autumn 2020

Optimization in Data Science, ETH Zurich, Spring 2020 (Head Assistant)

Algorithms, Probability, and Computing, ETH Zurich, Autumn 2019

Optimization in Data Science, ETH Zurich, Spring 2019

Talks

Drawings of Complete Multipartite Graphs Up to Triangle Flips Workshop on Combinatorial Reconfiguration, affiliated with ICALP 2023, Paderborn, Germany, Jul 2023

Zigzagging through acyclic orientations of graphs and hypergraphs Mittagsseminar, ETH Zürich, Switzerland, May 2023

Hardness of Approximating the Rank of a Graph Divisor Mittagsseminar, ETH Zürich, Switzerland, May 2022

Gioan's Theorem for complete bipartite graph Mittagsseminar, ETH Zürich, Switzerland, Dec 2021

A subexponential algorithm for ARRIVAL,

Assistance and interdiction problems on interval graphs Mittagsseminar, ETH Zürich, Switzerland, Nov 2020

Flip graph of combinatorial triangulations, Mittagsseminar, ETH Zürich, Switzerland, May 2020

ARRIVAL: A zero-player reachability switching game,

Combinatorial generation via permutation languages, ACM-SIAM Symposium on Discrete Algorithms 2020 (SODA20), Salt Lake City, UT, US, Jan 2020

Lattice quotients of the weak order, Mittagsseminar, ETH Zürich, Switzerland, Nov 2019

Exhaustive generation of pattern-avoiding permutations, Permutation Patterns 2019, Zurich, Switzerland, Jun 2019

Rank deficiency distribution of constrained random k-XORSAT matrix, ETH Zürich, Switzerland, Jul 2018

Supervised Theses

Lukas Egeling, Representation of Signotopes and Their Structures, Master CS, Mar 2024, with Helena Bergold and Bernd Gärtner

Ferdinand Nussbaum, Minimal and Maximal Elements of Lattice Congruences, Bachelor CS, Sep 2022

Lukas Hächler, Statistics for Tram Traffic Safety in Zurich, Master CS, Aug 2022, with Bernd Gärtner and Julia Hörrmann

Alain Bastian, Minimum partition into plane subgraphs, Master CS, Mar 2022, with Michael Hoffmann

Manuel Wiedmer, Reachability in the Hunger Game, Semester Thesis Maths, Sep 2021, with Bernd Gärtner

Chio Ge, The Multi-Run Procedure in ARRIVAL, Bachelor CS, Jul 2021, with Bernd Gärtner

Sebastian Haslebacher, Restrictions on ARRIVAL (part 2), Practical Work CS, Jan 2021, with Bernd Gärtner

Sebastian Haslebacher, Restrictions on ARRIVAL, Bachelor CS, Jul 2020, with Bernd Gärtner

Manuel Nowack, Minimum jump graph, Bachelor CS, Jul 2020, with Torsten Mütze

Janis Nertinger, One line and n points deterministically, Master Maths, Sep 2019, with Michael Hoffmann

Giovanni Compagnoni, Flip graphs of combinatorial triangulations, Master Maths, Sep 2019, with Michael Hoffmann

Jan Schilliger, Unique sink orientations and End of potential line, Bachelor CS, Jul 2019, with Bernd Gärtner

Jakob Roffler, Solving small unique sink orientations, Bachelor CS, Mar 2019, with Bernd Gärtner

(Potentially) Fun Facts