22 citations · 38 across the 9 of their papers we have counts for
13 papers
-server-bench: Automating Potential Discovery for the -Server Conjecture
Kirill Brilliantov, Etienne Bamas, Emmanuel Abbé
We introduce a code-based challenge for automated, open-ended mathematical discovery based on the -server conjecture, a central open problem in competitive analysis. The task is…
Randomized Rounding over Dynamic Programs
Etienne Bamas, Shi Li, Lars Rohwedder
We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constr…
The Submodular Santa Claus Problem
Etienne Bamas, Sarah Morell, Lars Rohwedder
We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Cla…
Lift-and-Project Integrality Gaps for Santa Claus
Etienne Bamas
This paper is devoted to the study of the MaxMinDegree Arborescence (MMDA) problem in layered directed graphs of depth , which is an important specia…
An Analysis of seeding for -means
Etienne Bamas, Sai Ganesh Nagarajan, Ola Svensson
One of the most popular clustering algorithms is the celebrated seeding algorithm (also know as -means++ when ) by Arthur and Vassilvitskii (2007), who showed that it…
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
Etienne Bamas, Marina Drygala, Ola Svensson
The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap -edge connecte…
An Improved Analysis of Greedy for Online Steiner Forest
Étienne Bamas, Marina Drygala, Andreas Maggiori
This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph and an arbitrary set of terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k…
The Submodular Santa Claus Problem in the Restricted Assignment Case
Etienne Bamas, Paritosh Garg, Lars Rohwedder
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned…
The Primal-Dual method for Learning Augmented Algorithms
Étienne Bamas, Andreas Maggiori, Ola Svensson
The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms…
Learning Augmented Energy Minimization via Speed Scaling
Étienne Bamas, Andreas Maggiori, Lars Rohwedder +1
As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a…
The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
Etienne Bamas, Paritosh Garg, Lars Rohwedder
We consider hypergraphs on vertices where each hyperedge contains exactly one vertex in . Our goal is to select a matching that covers all of , but we allow each se…
Local approximation of the Maximum Cut in regular graphs
Étienne Bamas, Louis Esperet
This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side…
Distributed coloring of graphs with an optimal number of colors
Étienne Bamas, Louis Esperet
This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e.\ with the minimum number of colors) in the LOCAL model of comput…