3 papers
cs.DS2018
Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid
Niv Buchbinder, Moran Feldman, Mohit Garg
We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ε)-approximation for th…
cs.DS2018
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…
cs.DS2015
Set Membership with a Few Bit Probes
Mohit Garg, Jaikumar Radhakrishnan
We consider the bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to…