57 citations · 154 across the 36 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
cs.DS2012
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Niv Buchbinder, Joseph, Naor +2
Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is…
cs.DS2012★ 6 cited
Geometry of Online Packing Linear Programs
Marco Molinaro, R. Ravi
We consider packing LP's with rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the…
cs.DS2012★ 3 cited
Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
Takuro Fukunaga, Zeev Nutov, R. Ravi
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iter…