Ernest van Wijland

PhD student at IRIF, Université Paris-Cité. I am fortunate to have Claire Mathieu (CNRS) and Vincent Cohen-Addad (Google Research) as my advisors.

My research interests include Optimization, Algorithms, and AI. I am currently working on AI's reasoning abilities, and on approximation algorithms for clustering and network design.

📄 My Resume

Email:

ernest(dot)vanwijland(at)irif(dot)fr

Publications (Google Scholar)

• TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability
  Cohen-Addad∗, Paparas∗, Van Wijland∗, Springer, Canitrot-Paradis, Lin, Woodruff, Kumarappan, Jayaram, Das, Jain, Svensson, Lattanzi, Balunovic, Weber, Mirrokni (*: co-first authors)
  In Submission
  Show Abstract
  We introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem-proving tasks from papers published at top theoretical computer science venues (STOC, FOCS, and SODA). Each task provides the necessary context to derive a self-contained proof for a target result. We evaluate state-of-the-art models on this benchmark. We verify the correctness of generated proofs via a verification agent, and further benchmark the verifier against human-expert proof judgements on a set of target statements and generated proofs pairs. Our reference verifier achieves over 90% accuracy on the expert labeled set. The tasks are publicly available here.
  AI Mathematics Benchmark
• Spectral Dual Fitting for \(k\)-Means
  Anand, Charikar, Cohen-Addad, Gao, Grandoni, Lee, Sharma, Van Wijland
  In Submission
  Show Abstract
  We give a new dual fitting algorithm which gives improved approximation ratios of \(3+\ln 2 + \varepsilon\ (\approx 3.694)\) and \(4.9+\varepsilon\) for \(k\)-Means in (high-dimensional) Euclidean and general metrics respectively, improving upon the previously known ratios of \(4+\varepsilon\) [Charikar, Cohen-Addad, Gao, Grandoni, Lee, and van Wijland STOC'26] and \(5+\varepsilon\) [Byrka, Guo, Hu, Li, Wan, Wang FOCS'26], resp. In particular, our result for Euclidean \(k\)-Means breaks the hardness barrier of \(1+8/e\approx 3.94\) for Metric \(k\)-Means. Prior to our work, no such separation between general and Euclidean metrics was known for \(k\)-Median, \(k\)-Means, or Facility Location in terms of their approximability.
  Unlike prior dual fitting approaches for \(k\)-Means, our new dual fitting algorithm tightly accounts for dual payments while still facilitating an effective dual feasibility analysis. We introduce a new framework that uses spectral analysis for determining the approximation factor of our algorithm.
  Clustering Dual Fitting Approximation Algorithms
• Beyond Worst-Case Online Multi-Level Aggregation
  Mathieu, Naor, Van Wijland
  In Submission
  Show Abstract
  Aggregation is a classic problem in network design. Here, we study one of its most famous variants, the online Multi-Level Aggregation problem with Deadlines (MLAP-D). Given a rooted tree with node costs, requests arrive over time at the tree nodes, each request must be served by its deadline, and requests that are pending at a common time can be aggregated and served together. The cost of serving a set of requests together is the total cost of the minimal subtree spanning all nodes containing those requests (and the root), and the objective is to minimize the sum of the costs of the nodes in the subtrees used to serve all requests.
  The best known online algorithms are \(O(\hbox{depth})\)-competitive, whereas the strongest known online lower bound is \(4\)-competitiveness. In this paper, we initiate the theoretical study of MLAP-D beyond the worst-case setting. Leveraging the existence and structure of a constant approximation algorithm in the offline setting, we consider a simple online algorithm, \(SampleAndAugment\), and prove that for three natural stochastic models, it is \(4\)-competitive in expectation. This matches the adversarial setting lower bound. We complement these results with reductions demonstrating that our stochastic assumptions are necessary; if they are relaxed, the problem remains as difficult as the general worst-case adversarial setting.
  Online Algorithms Network Design Stochastic
• A \((4+\varepsilon)\)-Approximation for Euclidean \(k\)-Means via Non-Monotone Dual Fitting
  Charikar, Cohen-Addad, Gao, Grandoni, Lee, Van Wijland
  STOC 2026
  Show Abstract
  We present a polynomial-time \( (4+\varepsilon) \)-approximation algorithm for (high-dimensional) Euclidean \( k \)-Means. This substantially improves on the current-best 5.83-approximation in [Charikar, Cohen-Addad, Gao, Grandoni, Lee, Van Wijland - FOCS'25] (that also works for the metric case).
  The mentioned algorithm by Charikar et al. critically exploits a greedy Lagrangian Multiplier Preserving (LMP) approximation for Facility Location with squared metric distances, that adapts the classical greedy algorithm with dual-fitting analysis for Metric Facility Location in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM'03]. The authors then turn it into an approximation algorithm for (Metric) \( k \)-Means, at the cost on an extra factor \( 1+\varepsilon \), by exploiting the framework introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC'25] for \( k \)-Median.
  Our main contribution is a greedy LMP 4-approximation for Facility Location with squared Euclidean distances. Differently from Charikar et al., our algorithm sometimes decreases the dual variables, a quite uncommon feature for dual-based algorithms. This is critical in our dual-fitting analysis in order to exploit the specific properties of Euclidean metrics. For the \( (4+\varepsilon) \)-approximation for \( k \)-Means, we extend the framework by Cohen-Addad et al. by overcoming substantial technical challenges posed by decreased dual values.
  Clustering Dual Fitting Approximation Algorithms
• An Improved Greedy Approximation for (Metric) \(k\)-Means
  Charikar, Cohen-Addad, Gao, Grandoni, Lee, Van Wijland
  FOCS 2025
  Show Abstract
  Clustering is a basic task in data analysis and machine learning, and the optimization of clustering objectives are well-studied optimization problems; amongst these, the \( k \)-Means objective is arguably the most well known. Given a collection of points in a metric space, the goal is to partition them into \( k \) clusters, each with an associated center, so as to minimize the sum of squared distances of points to their cluster centers.
  In this paper, we present a polynomial-time \( 3+2\sqrt{2}+\varepsilon<5.83 \)-approximation algorithm for \( k \)-Means in general metrics. This substantially improves on the current-best \( (9+\varepsilon) \)-approximation in [Ahmadian, Norouzi-Fard, Svensson, Ward - FOCS'17, SICOMP'20], and even slightly improves on the \(5.92\)-approximation in [Cohen-Addad, Esfandiari, Mirrokni, Narayanan - STOC'22] for the Euclidean special case.
  A natural approach for \( k \)-Means is to leverage Lagrangian Multiplier Preserving (LMP) approximations for the facility location problem. The previous best results for \( k \)-Means build upon an adaptation of an LMP \(3\)-approximation for facility location with metric connection costs in [Jain, Vazirani - J.ACM'01] based on a primal-dual method, rather than on the improved LMP greedy \(2\)-approximation for the same problem in [Jain, Mahdian, Markakis, Saberi, Vazirani - J.ACM'03]. The barrier to using the improved LMP algorithm was that no adaptation of this algorithm and its analysis to the case of squared metric connection costs was known (since squared distances violate triangle inequality). Our main contribution is overcoming this barrier by providing such an adaptation. This new LMP approximation algorithm is then combined with the framework recently introduced in [Cohen-Addad, Grandoni, Lee, Schwiegelshohn, Svensson - STOC'25] for the related (metric) \( k \)-Median problem.
  Clustering Dual Fitting Approximation Algorithms
• Faster Approximation Scheme for Euclidean \(k\)-TSP
  Van Wijland, Zhou
  SOCG 2024
  Show Abstract
  In the Euclidean \( k \)-traveling salesman problem (\( k \)-TSP), we are given \( n \) points in the \( d \)-dimensional Euclidean space, for some fixed constant \( d \geq 2 \), and a positive integer \( k \). The goal is to find a shortest tour visiting at least \( k \) points. We give an approximation scheme for the Euclidean \( k \)-TSP in time \( n \cdot 2^{O(1/\varepsilon^{d-1})} \cdot (\log n)^{2d^2 \cdot 2^d} \). This improves Arora's approximation scheme of running time \( n \cdot k \cdot (\log n)^{\left(O\left(\sqrt{d}/\varepsilon\right)\right)^{d-1}} \) [J. ACM 1998]. Our algorithm is Gap-ETH tight and can be derandomized by increasing the running time by a factor \( O(n^d) \).
  Vehicle Routing Computational Geometry Approximation Algorithms
• Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability
  Akrami, Chaudhury, Hoefer, Mehlhorn, Schmalhofer, Shahkarami, Varricchio, Vermande, Van Wijland
  MOOR 2023
  Show Abstract
  We study the problem of allocating a set of indivisible goods among a set of agents with two-value additive valuations. In this setting, each good is valued either \(1\) or \( p/q \) for some fixed coprime numbers \( p, q \in \mathbb{N} \) such that \( 1 \leq q < p \). Our goal is to find an allocation that maximizes the Nash social welfare (NSW), that is, the geometric mean of the valuations of the agents. In this work, we give a complete characterization of polynomial-time tractability of NSW maximization that solely depends on the value of \( q \). We start by providing a rather simple polynomial-time algorithm to find a maximum NSW allocation when the valuation functions are integral, that is, \( q = 1 \). We then exploit more involved techniques to get an algorithm that produces a maximum NSW allocation for the half-integral case, that is, \( q = 2 \). Finally, we show it is NP-hard to compute an allocation with maximum NSW whenever \( q \geq 3 \).
  Fair Division Game Theory Approximation Algorithms
• Maximizing Nash Social Welfare in 2-Value Instances
  Akrami, Chaudhury, Hoefer, Mehlhorn, Schmalhofer, Shahkarami, Varricchio, Vermande, Van Wijland
  AAAI 2022
  Show Abstract
  We consider the problem of maximizing the Nash social welfare when allocating a set \( G \) of indivisible goods to a set \( N \) of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either \( p \) or \( q \), where \( p \) and \( q \) are integers and \( p \ge 2 \). In terms of approximation, we present positive and negative results for general \( p \) and \( q \). We show that our algorithm obtains an approximation ratio of at most \(1.0345\). Moreover, we prove that the problem is APX-hard, with a lower bound of \(1.000015\) achieved at \( p/q = 4/5 \).
  Fair Division Game Theory Approximation Algorithms

Teaching

• Currently teaching assistant for the second year of Bachelor course "Programming Project" at Université Paris-Cité.
• Previously teaching assistant for the "Introduction to Python", "Algorithmics Concepts", and "Programming Project" courses.