39 citations · 180 across the 62 of their papers we have counts for
5 papers · 1 filter
Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
Yuval Filmus, Roy Schwartz, Alexander V. Smal
We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy…
Asymptotic performance of the Grimmett-McDiarmid heuristic
Yuval Filmus
Grimmett and McDiarmid suggested a simple heuristic for finding stable sets in random graphs. They showed that the heuristic finds a stable set of size (with high pr…
The entropy of lies: playing twenty questions with a liar
Yuval Dagan, Yuval Filmus, Daniel Kane +1
`Twenty questions' is a guessing game played by two players: Bob thinks of an integer between and , and Alice's goal is to recover it using a minimal number of Yes/No questi…
Online Submodular Maximization: Beating 1/2 Made Simple
Niv Buchbinder, Moran Feldman, Yuval Filmus +1
The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively from both computational and economic per…
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Yuval Filmus, Justin Ward
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Cali…