## Paul Fermé

### Modèles de calcul, Complexité, Combinatoire

I am currently working on my PhD thesis under the direction of Omar Fawzi in the team MC2 at LIP (ENS de Lyon). I am mainly interested in the algorithmic aspects of quantum communication. I am also interested in quantum information in general, as well as approximation algorithms and algorithmic game theory.

### Interests

• Quantum Information
• Approximation Algorithms
• Algorithmic Game Theory

### Education

• M2 in Computer Science, 2016

École Normale Supérieure de Lyon

• L3 in Computer Science, 2014

École Normale Supérieure de Lyon

# Publications

### Tight Approximation Guarantees for Concave Coverage Problems (STACS 2021)

In the maximum coverage problem, we are given subsets $T_1, \ldots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := |\bigcup_{i \in S} T_i|$. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of $1-e^{-1}$.

In this work we consider a generalization of this problem wherein an element $a$ can contribute by an amount that depends on the number of times it is covered. Given a concave, nondecreasing function $\varphi$, we define $C^{\varphi}(S) := \sum_{a \in [n]} w_a\varphi(|S|_a)$, where $|S|_a = |{i \in S : a \in T_i}|$. The standard maximum coverage problem corresponds to taking $\varphi(j) = \min(j,1)$. For any such $\varphi$, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of $\varphi$, defined by $\alpha_{\varphi} := \min_{x \in \mathbb{N}^*} \frac{E[\varphi(Poi(x))]}{\varphi(E[Poi(x)])}$. Complementing this approximation guarantee, we establish a matching NP-hardness result when $\varphi$ grows in a sublinear way.

As special cases, we improve the result of Barman et al., IPCO, 2020 about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of Dudycz et al., IJCAI, 2020 on multi-winner approval-based voting for geometrically dominant rules. Our result goes beyond these special cases and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.

# Teaching

## 2020-2021

### ALGO 1 (L3)

#### DMs

À propos de la méthode de l’adversaire : c’est bien expliqué sur ce site, et en particulier les 10 premières minutes de cette vidéo.

### Information Theory (M1)

Here, some nice video on Hamming codes