A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems

Andrés Fielbaum, Ignacio Morales, José Verschae

Obtaining strong linear relaxations of capacitated covering problems constitute a major technical challenge even for simple settings. For one of the most basic cases, the Knapsack-…