Hang Zhou

Professor
Department of Computer Science
École Polytechnique, France

Email: zhouhang32 (at) gmail.com

My research is on combinatorial optimization, graph algorithms, and operations research.

I received my PhD from the École Normale Supérieure de Paris. I was very fortunate to have Claire Mathieu as my PhD advisor. Afterwards, I was a postdoctoral researcher at the Max-Planck-Institut für Informatik in Germany, and I was very lucky to be hosted by Kurt Mehlhorn.

I received the Lise Meitner Award for excellent women in computer science.

An article (in French) from CNRS on my work on the optimization can be found here.

Member of program committees: ICALP'25, STACS'24, SOSA'23.

Publications

Author list is in alphabetical order as is customary in theoretical computer science.

Conference Papers

Euclidean Capacitated Vehicle Routing in the Random Setting: A 1.55-Approximation Algorithm.
Zipei Nie and Hang Zhou.
European Symposium on Algorithms (ESA), 2024, slides.
Faster Approximation Scheme for Euclidean k-TSP.
Ernest van Wijland and Hang Zhou.
International Symposium on Computational Geometry (SoCG), 2024.
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, slides.
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 Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees.
Claire Mathieu and Hang Zhou.
Mathematical Programming, 2024.
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.