596 citations · 3k across the 50 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
cs.DS2008★ 23 cited
Greedy D-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Christos Koufogiannakis, Neal E. Young
This paper describes a simple greedy D-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be…
cs.DS2008★ 48 cited
A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
Christos Koufogiannakis, Neal E. Young
We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, an…