Distributed Set Cover Approximation: Primal-Dual with Optimal Locality.
Guy EvenMohsen GhaffariMoti MedinaPublished in: DISC (2018)
Keyphrases
- set cover
- primal dual
- approximation algorithms
- worst case
- greedy heuristics
- minimum cost
- linear programming
- affine scaling
- np hard
- simplex algorithm
- linear programming problems
- special case
- approximation guarantees
- variational inequalities
- convex optimization
- greedy algorithm
- linear program
- greedy heuristic
- interior point methods
- convergence rate
- interior point algorithm
- semidefinite programming
- algorithm for linear programming
- optimal solution
- simplex method
- interior point
- convex functions
- dynamic programming
- network flow
- integrality gap
- cost function
- lower bound
- image processing