85 citations · 237 across the 30 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012★ 3 cited
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc dis…
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…