Hang Zhou

Professor at École Polytechnique

zhouhang32 (at) gmail.com

I am a professor in the Computer Science department at the École Polytechnique. My research is mainly 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.

ICPC: I was the coach of the École Polytechnique team that won the championship in European programming competition (SWERC), the first championship in École Polytechnique's history, as well as eight medals, and three times advanced to the World Finals.

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

Publications

In my field, the authors are usually listed in alphabetical order.
Preprints
- Faster Approximation Schemes for k-TSP and k-MST in the Euclidean Space.
  Ernest van Wijland and Hang Zhou.
- Euclidean Capacitated Vehicle Routing in Random Setting: A 1.55-Approximation Algorithm.
  Zipei Nie and Hang Zhou.
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, 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 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.

Publications

Preprints

Conference Papers

Journal Papers