5 citations · 6 across the 3 of their papers we have counts for
3 papers · 1 filter
When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Jian Li +3
Consider a random graph model where each possible edge is present independently with some probability . Given these probabilities, we want to build a large/heavy matching…
Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms
Anupam Gupta, Aaron Roth, Grant Schoenebeck +1
Constrained submodular maximization problems have long been studied, with near-optimal results known under a variety of constraints when the submodular function is monotone. The ca…
When LP is the Cure for Your Matching Woes: Approximating Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Viswanath Nagarajan +1
This results in this paper have been merged with the result in arXiv:1002.3763v1 The authors would like to withdraw this version. Please see arXiv:1008.5356v1 for the merged versio…