A water filling primal dual algorithm for approximating non linear covering problems (2022)

Simple item page
dc.contributor.authorFielbaum, Andres
dc.contributor.authorMorales, Ignacio
dc.contributor.authorVerschae, Jose
dc.date.accessioned2025-01-20T21:00:50Z
dc.date.available2025-01-20T21:00:50Z
dc.date.issued2022
dc.description.abstractObtaining strong linear relaxations for capacitated covering problems constitutes a significant technical challenge. For one of the most basic cases, the relaxation based on knapsackcover inequalities has an integrality gap of 2. We generalize the setting considering items that can be taken fractionally to cover a given demand, with a cost given by an arbitrary nondecreasing function (not necessarily convex) of the chosen fraction. We generalize the knapsack-cover inequalities and use them to obtain a polynomial (2 + epsilon)-approximation algorithm. Our primal-dual procedure has a natural interpretation as a water-filling algorithm, which overcomes the difficulties implied by having different growth rates in the cost functions: when the cost of an item increases slowly at some superior segment, it carefully increases the priority of all preceding segments. We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for fractional items with nonlinear costs. We obtain a 4-approximation in pseudopolynomial time (4 + epsilon in polynomial time),matching the approximation ratio of the classical setting. We also present a rounding algorithm with an approximation guarantee of 2. This result is coupled with a polynomial time separation algorithm that allows solving our linear relaxation up to a loss of a (1 + epsilon) factor.
dc.description.funderFondecyt Project
dc.fuente.origenWOS
dc.identifier.doi10.1137/21M1459964
dc.identifier.eissn1095-7146
dc.identifier.issn0895-4801
dc.identifier.urihttps://doi.org/10.1137/21M1459964
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/92750
dc.identifier.wosidWOS:000934152600018
dc.issue.numero4
dc.language.isoen
dc.pagina.final2915
dc.pagina.inicio2889
dc.revistaSiam journal on discrete mathematics
dc.rightsacceso restringido
dc.subjectknapsack-cover inequalities
dc.subjectnonlinear knapsack-cover
dc.subjectprimal-dual
dc.subjectwater-filling algorithm
dc.titleA water filling primal dual algorithm for approximating non linear covering problems (2022)
dc.typeartículo
dc.volumen36
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas