
Hang Zhou
Tenured Assistant Professor with Habilitation
zhouhang32 (at) gmail.com
I am a tenured assistant professor in the Computer Science department at the École Polytechnique.
My research is mainly on combinatorial optimization, graph algorithms, and operations research.
I obtained my habilitation in 2022. Committee members: Nikhil Bansal (reviewer), Benjamin Doerr, Marc Lelarge (president), Claire Mathieu, Kurt Mehlhorn (reviewer), Thomas Sauerwald, and Jens Vygen (reviewer).
I received my PhD degree from the École Normale Supérieure de Paris.
I was very fortunate to have Claire Mathieu as my PhD advisor.
Afterwards, I spent two years as a postdoctoral researcher at the Max-Planck-Institut für Informatik in Germany.
I was very lucky to be hosted by Kurt Mehlhorn.
I received the Lise Meitner Award for excellent women in computer science.
Between 2017 and 2022, I was the coach of the École Polytechnique team that won the championship and eight medals in European programming competitions (ICPC SWERC) and twice advanced to the World Finals.
I was a member of the program committee of SIAM SOSA 2023.
Supervision
I have the pleasure to advice and learn from the following students:-
- Ernest van Wijland (Master, ENS Paris), 2023.
- Noé Weeks (Master, ENS Paris), 2023.
- Pedro Cabral (Bachelor, Polytechnique), 2022.
- Marc Dufay (Master, Polytechnique), 2022. Research internship award from the Académie des Sciences.
Co-advised with Claire Mathieu. - Khanh Nguyen (Bachelor, Polytechnique), 2021.
- Antoine Stark (Master, Polytechnique), 2021.
Publications
- In my field, the authors are usually listed in alphabetical order.
-
In Submission
-
Euclidean Capacitated Vehicle Routing in Random Setting: A 1.55-Approximation Algorithm.
Zipei Nie and Hang Zhou.
Submitted to FOCS 2023.
Conference Papers
-
A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees.
Claire Mathieu and Hang Zhou.
International Colloquium on Automata, Languages and Programming (ICALP), 2023. -
Capacitated Vehicle Routing in Graphic Metrics.
Tobias Mömke and Hang Zhou.
SIAM Symposium on Simplicity in Algorithms (SOSA), 2023, slides. -
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees.
Marc Dufay, Claire Mathieu, and Hang Zhou.
International Symposium on Theoretical Aspects of Computer Science (STACS), 2023. -
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm.
Fabrizio Grandoni, Claire Mathieu, and Hang Zhou.
Innovations in Theoretical Computer Science (ITCS), 2023, slides. -
A PTAS for Capacitated Vehicle Routing on Trees.
Claire Mathieu and Hang Zhou.
International Colloquium on Automata, Languages and Programming (ICALP), 2022, slides. -
A Simple Algorithm for Graph Reconstruction.
Claire Mathieu and Hang Zhou.
European Symposium on Algorithms (ESA), 2021, slides. -
Probabilistic Analysis of Euclidean Capacitated Vehicle Routing.
Claire Mathieu and Hang Zhou.
International Symposium on Algorithms and Computation (ISAAC), 2021, slides. -
A (5/3+ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes.
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou.
ACM Symposium on Theory of Computing (STOC), 2018, slides. -
Optimization of Bootstrapping in Circuits.
Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, and Hang Zhou.
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, slides. -
To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack.
Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou.
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017, slides. -
Near-Linear Query Complexity for Graph Inference.
Sampath Kannan, Claire Mathieu, and Hang Zhou.
International Colloquium on Automata, Languages and Programming (ICALP), 2015, slides. -
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs.
Philip Klein, Claire Mathieu, and Hang Zhou.
International Symposium on Theoretical Aspects of Computer Science (STACS), 2015, slides. -
Graph Reconstruction via Distance Oracles.
Claire Mathieu and Hang Zhou.
International Colloquium on Automata, Languages and Programming (ICALP), 2013, slides. -
Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs.
Marc Lelarge and Hang Zhou.
International Symposium on Algorithms and Computation (ISAAC), 2013, slides.
Journal Papers
- A PTAS for Capacitated Vehicle Routing on Trees.
Claire Mathieu and Hang Zhou.
ACM Transactions on Algorithms (TALG), 2023. -
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs.
Philip Klein, Claire Mathieu, and Hang Zhou.
Algorithmica, 2023. -
A Simple Algorithm for Graph Reconstruction.
Claire Mathieu and Hang Zhou.
Random Structures & Algorithms (RSA), 2023. -
Iterated Tour Partitioning for Euclidean Capacitated Vehicle Routing.
Claire Mathieu and Hang Zhou.
Random Structures & Algorithms (RSA), 2022. -
Graph Reconstruction and Verification.
Sampath Kannan, Claire Mathieu, and Hang Zhou.
ACM Transactions on Algorithms (TALG), 2018. -
Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs.
Marc Lelarge and Hang Zhou.
Theoretical Computer Science (TCS), 2014. -
Backtracking-Assisted Multiplication.
Houda Ferradi, Rémi Géraud, Diana Maimut, David Naccache, and Hang Zhou.
Journal of Cryptography and Communications, 2018.
-
Euclidean Capacitated Vehicle Routing in Random Setting: A 1.55-Approximation Algorithm.