Publications

On every ANR publication we need to write the following sentence:
"This work was [partially] funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR)."

The following publications were partially funded by ANR.

2020

1. How to aggregate Top-lists: Approximation algorithms via scores and average ranks,
   Claire Mathieu, Simon Mauras, SODA'20
2. LP-based algorithms for multistage minimization problems,
   Evripidis Bampis, Bruno Escoffier, Alexander Kononov, WAOA'20
3. Lp Pattern Matching in a Stream,
   Tatiana Starikovskaya, Michal Svagerka, Przemysław Uznański, APPROX/RANDOM 2020
4. Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs,
   Andreas .E. Feldmann, David Saulpic, ESA 2020 and Journal of Computer and System Sciences.
5. Large Very Dense Subgraphs in a Stream of Edges,
   Claire Mathieu, Michel de Rougemont: FODS 2020: 107-117

2021

1. Extension of Gyarfas-Sumner conjecture to digraphs ,
   P. Aboulker, P. Charbit, R. Naserasr, Electron. J. Comb. 28(2): P2.27 (2021).
2. On the dichromatic number of surfaces. ,
   P. Aboulker, F. Havet, K. Knauer, C. Rambaud, accepted in EUROCOMB 2021.
3. Decomposing and colouring some locally semicomplete digraphs. ,
   P. Aboulker, G. Aubian, P. Charbit, accepted in EUROCOMB 2021.
4. Online Multistage Subset Maximization Problems,
   Evripidis Bampis, Bruno Escoffier, Kevin Schewior, Alexandre Teiller, Algorithmica 83(8): 2374-2399 (2021).
5. A New Coreset Framework for Clustering,
   Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn, STOC 2021
6. Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages,
   Gabriel Bathie, Tatiana Starikovskaya, ICALP 2021
7. Orienting (hyper)graphs under explorable stochastic uncertainty,
   Evripidis Bampis, Thomas Erlebach, Christoph Dürr, Murilo S. de Lima, Nicole Megow, Jens Schlöter. ESA 2021.
8. Randomized Two-Valued Bounded Delay Online Buffer Management,
   Christoph Dürr, Shahin Kamali. Operations Research Letters, 49(2): 246-249, 2021.
9. Online Search With a Hint,
   Spyros Angelopoulos, ITCS 2021
10. Speed Scaling with Explorable Uncertainty,
    Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, Fanny Pascual, SPAA 2021
11. A Simple Algorithm for Graph Reconstruction,
    Claire Mathieu, Hang Zhou. ESA 2021: 68:1-68:18
12. Two-Sided Matching Markets with Strongly Correlated Preferences,
    Hugo Gimbert, Claire Mathieu, Simon Mauras. FCT 2021: 3-17
13. Approximating Maximum Integral Multiflows on Bounded Genus Graphs,
    Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen. ICALP 2021: 80:1-80:18
14. Probabilistic Analysis of Euclidean Capacitated Vehicle Routing,
    Claire Mathieu, Hang Zhou. ISAAC 2021: 43:1-43:16
15. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces,
    Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
    NeurIPS 2021 (spotlight)
16. On the tree-width of even-hole-free graphs,
    P. Aboulker, I. Adler, E-J Kim, N.L.D. Sintiari and N. Trotignon, European Journal of Combinatorics, December 2021.
17. Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics,
    Vincent Cohen-Addad, Andreas E. Feldmann, David Saulpic, Journal of the ACM, December 2021.

2022

1. Graphs with no induced house nor induced hole have the de Bruijn-Erdős property,
   P. Aboulker, L. Beaudou, M. Matamala, J. Zamora, Journal of Graph Theory, January 2022.
2. Online Search With Best-Price and Query-Based Predictions ,
   Spyros Angelopoulos, Shahin Kamali, Dehou Zhang, AAAI 2022.
3. Online Bin Packing with Predictions ,
   Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami, IJCAI 2022.
4. An Improved Local Search Algorithm for k-Median ,
   Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, David Saulpic. SODA 2022.
5. Towards Optimal Lower Bounds for k-median and k-means Coresets,
   Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn.
   STOC 2022 .
6. Scheduling with a processing time oracle,
   Christoph Dürr, Fanny Dufossé, Noël Nadal, Denis Trystram and Óscar C. Vásquez. Applied Mathematical Modelling, 104: 701-720, 2022.

2023

1. A PTAS for Capacitated Vehicle Routing on Trees,
   Claire Mathieu, Hang Zhou. ACM Trans. Algorithms 19(2): 17:1-17:28 (2023). (Conference version: Claire Mathieu, Hang Zhou:
   A PTAS for Capacitated Vehicle Routing on Trees. ICALP 2022: 95:1-95:20)
2. A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees,
   Claire Mathieu, Hang Zhou. ICALP 2023: 91:1-91:16
3. Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm,
   Fabrizio Grandoni, Claire Mathieu, Hang Zhou. ITCS 2023: 63:1-63:13
4. An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees,
   Marc Dufay, Claire Mathieu, Hang Zhou. STACS 2023: 27:1-27:16