48 citations · 102 across the 3 of their papers we have counts for
3 papers
cs.DS2020★ 31 cited
Distributed algorithms for covering, packing and maximum weighted matching
Christos Koufogiannakis, Neal E. Young
This paper gives poly-logarithmic-round, distributed D-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Coveri…
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…