6 citations · 9 across the 9 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
On the Average-Case Performance of Greedy for Maximum Coverage
Eric Balkanski, Jason Chatzitheodorou, Flore Sentenac
For the classical maximum coverage problem, the greedy algorithm achieves a worst-case approximation, which is optimal unless . The notion of coverage…
cs.DS2023
Online Matching in Geometric Random Graphs
Flore Sentenac, Nathan Noiry, Matthieu Lerasle +2
We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any p…
cs.DS2021
Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
Nathan Noiry, Flore Sentenac, Vianney Perchet
Motivated by sequential budgeted allocation problems, we investigate online matching problems where connections between vertices are not i.i.d., but they have fixed degree distribu…