3 citations · 3 across the 4 of their papers we have counts for
7 papers
Optimal compression with quantum retrieval
Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar +1
We consider the following data compression problem. Given a string of Hamming weight at most , compress it into a shorter string so that any…
Matching Augmentation via Simultaneous Contractions
Mohit Garg, Felix Hommelsheim, Nicole Megow
We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a -edge-connected spanning subgraph by adding the minimum number of ed…
Improved Approximation for Two-Edge-Connectivity
Mohit Garg, Fabrizio Grandoni, Afrouz Jabal Ameli
The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edg…
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…
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…
Set membership with non-adaptive bit probes
Mohit Garg, Jaikumar Radhakrishnan
We consider the non-adaptive 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 vecto…