Welcome!

I am a post-doc at the University of Copenhagen in the Centre for Efficient Algorithms and Data Structures (EADS), hosted by Prof. Mikkel Thorup.
I did my Ph.D at the Département d'Informatique de l'École normale supérieure. I was very fortunate to have Prof. Claire Mathieu and Prof. Zhentao Li as my advisors. I have a broad interest in the design and analysis of algorithms. I have been working on approximation algorithms for NP-Hard problems with emphasis on clustering and network design problems, planar graphs problems, algorithmic game theory and scheduling. I am also interested in graph theory.

My CV in pdf.

News: I wrote a popular science article (in french) about some of my results for the blog of the Société Informatique de France hosted by the french newspaper Le Monde, check it out!

Publications

  • Online Optimization of Smoothed Piecewise Constant Functions

    Joint work with Varun Kanade

    ArXiv - Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS) 2017.

    Click to show the abstract.

    We study online optimization of smoothed piecewise constant functions over the domain [0, 1). This is motivated by the problem of adaptively picking parameters of learning algorithms as in the recently introduced framework by Gupta and Roughgarden. Majority of the machine learning literature has focused on Lipschitz-continuous functions or functions with bounded gradients. This is with good reason -- any learning algorithm suffers linear regret even against piecewise constant functions that are chosen adversarially, arguably the simplest of non-Lipschitz continuous functions. The smoothed setting we consider is inspired by the seminal work of Spielman and Teng and the recent work of Gupta and Roughgarden in this setting, the sequence of functions may be chosen by an adversary, however, with some uncertainty in the location of discontinuities. We give algorithms that achieve sublinear regret in the full information and bandit settings.

  • Steinberg's Conjecture is false

    Joint work with Michael Hebdige, Daniel Kral, Zhentao Li, and Esteban Salgado

    ArXiv - To appear in Journal of Combinatorial Theory, Series B (JCTB), 2017.
    See also this article (in french) in the popular science magazine "Pour la Science".

    Click to show the abstract.

    Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.

  • Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics

    Joint work with Philip N. Klein, and Claire Mathieu.

    ArXiv - Proceedings of the Symposium on Foundations of Computer Science (FOCS) 2016.

    Click to show the abstract.

    We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) k-median and k-means in edge-weighted planar graphs; (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the p-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/epsilon^O(1) centers.

  • The Invisible Hand of Dynamic Market Pricing

    Joint work with Alon Eden, Michal Feldman, and Amos Fiat.

    ArXiv - To appear in the Proceedings of the Conference on Economics and Computation (EC) 2016.

    Click to show the abstract.

    Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortu- nately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrar- ily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done.

  • Diameter and k-Center Clustering in Sliding Window

    Joint work with Chris Schwiegelshohn, and Christian Sohler.

    To appear in the Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) 2016.

    Click to show the abstract.

    In this paper, we investigate small space summaries for diameter and k-center clus- tering in sliding windows. In particular, we give an algorithm maintaining a 3 + epsilon approximate diameter, i.e. the maximum distance between two input points, in arbitrary metric spaces with nearly optimal space requirements. Furthermore, we investigate the related problem of k-center clustering, i.e. the covering of the input with k balls of minimum radius. For k = 2 we give a sliding window algorithm with optimal approximation ratio 4 + epsilon and for arbitrary values of k, algorithms with approximation ratio 6 + epsilon in general metric spaces and 4.48 in Euclidean spaces. In the metric distance model it is assumed that any algorithm with space x can store at most x points and that it cannot generate new points that are distinct from the stored points except by reading from the input stream. Under this assumptions, we obtain lower bounds that separate the space complexity for sliding window algorithm from insertion-only algorithms by an exponential factor. To our knowledge, no such separation was previously known.

  • Approximating Connectivity Domination in Weighted Bounded-Genus Graphs

    Joint work with Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld.

    Proceedings of the Symposium on Theory of Computing (STOC) 2016.

    Click to show the abstract.

    We present a framework for addressing several problems on weighted planar graphs and graphs of bounded genus. With that framework, we derive polynomial-time approximation schemes for the following problems in planar graphs or graphs of bounded genus: edge-weighted tree cover and tour cover; vertex-weighted connected dominating set, maximum-weight-leaf spanning tree, and connected vertex cover. In addition, we obtain a polynomial-time approximation scheme for feedback vertex set in planar graphs. These are the first polynomial-time approximation schemes for all those problems in weighted embedded graphs. (For unweighted versions of some of these problems, poynomial-time approximation schemes were previously given using bidimensionality.) Additionally, we design a quasi- polynomial-time approximation scheme for weighted connected face cover in planar graphs, which implies a quasi-polynomial-time approximation scheme for the minimum corridor problem, a problem in the plane.

  • Algorithmic Aspects of Switch Cographs

    Joint work with Michel Habib and Fabien de Montgolfier.

    ArXiv - Discrete Applied Mathematics, vol. 200. 2016.

    Click to show the abstract.

    We introduced the notion of involution module, the first generalization of modular decomposition which has a unique linear-sized decomposition tree in the general context of 2-structures. We derived O(n²) decomposition algorithm and we take advantage of the involution modular decomposition tree to state several algorithmic results. We introduced the class of switch cographs, the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and is exactly the class of (Bull, Gem, Co-Gem, C5)-free graphs. We used our new decomposition tool to design three practical algorithms for the maximum cut and the vertex separator problems. The complexity of these problems was still unknown for this class of graphs. We also improved the complexity of the maximum clique, the maximum independant set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we showed that this class of graphs has Clique-Width at most 4 and that a clique-width expression can be computed in linear time.

  • A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface

    Joint work with Arnaud de Mesmay.

    ArXiv - Proceedings of the European Symposium on Algorithms (ESA) 2015.

    Click to show the abstract.

    Given a graph G cellularly embedded on a surface S of genus g, a cut graph is a subgraph of G such that cutting S along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any epsilon > 0, we show how to compute a (1 + epsilon) approximation of the shortest cut graph in time f (epsilon, g)n^3 . Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest

  • Effectiveness of Local Search for Geometric Optimization.

    Joint work with Claire Mathieu.

    ArXiv - Proceedings of the Symposium on Computational Geometry (SoCG) 2015.

    Click to show the abstract.

    We prove that local search with local neighborhoods of magnitude of 1/epsilon^C is an approximation scheme for the following problems in the Euclidian plane: TSP with random inputs, Steiner tree with random inputs, facility location (with worst case inputs), and bicriteria k-median (also with worst case inputs). We show that the randomness assumption is necessary for TSP

  • Energy-Efficient Algorithms for Non-Preemptive Speed-Scaling

    Joint work with Zhentao Li, Claire Mathieu, and Ioannis Milis.

    ArXiv - Proceedings of the Workshop on Approximation and Online Algorithms (WAOA) - 2014.

    Click to show the abstract.

    We improve complexity bounds for energy-efficient speed scheduling problems for both the single processor and multi-processor cases. Energy conservation has become a major concern, so revisiting traditional scheduling problems to take into account the energy consumption has been part of the agenda of the scheduling community for the past few years. We consider the energy minimizing speed scaling problem introduced by Yao et al. where we wish to schedule a set of jobs, each with a release date, deadline and work volume, on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the αth power of its speed. The objective is then to find a feasible schedule which minimizes the total energy used. We show that in the setting with an arbitrary number of processors where all work volumes are equal, there is a 2(1+\varepsilon)(5(1+\varepsilon))\alpha−1B_\alpha=O_\alpha(1) approximation algorithm, where B_\alpha is the generalized Bell number. This is the first constant factor algorithm for this problem. This algorithm extends to general unequal processor-dependent work volumes, up to losing a factor of (((1+r)r)^\alpha)/2 in the approximation, where r is the maximum ratio between two work volumes. We then show this latter problem is APX-hard, even in the special case when all release dates and deadlines are equal and r is 4. In the single processor case, we introduce a new linear programming formulation of speed scaling and prove that its integrality gap is at most 12^(\alpha−1). As a corollary, we obtain a (12(1+\varepsilon))^(\alpha−1) approximation algorithm where there is a single processor, improving on the previous best bound of 2^{\alpha−1)(1+\varepsilon)^\alpha B_\alpha when \alpha > 24.