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

Simple item page
dc.catalogadoryvc
dc.contributor.authorFielbaum, Andrés
dc.contributor.authorMorales Bravo Camilo Ignacio
dc.contributor.authorVerschae Tannenbaum Jose Claudio
dc.date.accessioned2025-02-24T19:40:48Z
dc.date.available2025-02-24T19:40:48Z
dc.date.issued2020
dc.description.abstractObtaining strong linear relaxations of capacitated covering problems constitute a significant technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. These inequalities are exploited in more general problems, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a general setting in which items can be taken fractionally to cover a given demand. The cost incurred by an item is given by an arbitrary non-decreasing function of the chosen fraction. We generalize the knapsack-cover inequalities to this setting an use them to obtain a (2+ε)-approximate primal-dual algorithm. Our procedure has a natural interpretation as a bucket-filling algorithm which effectively overcomes the difficulties implied by having different slopes in the cost functions. More precisely, when some superior segment of an item presents a low slope, it helps to increase the priority of inferior segments. We also present a rounding algorithm with an approximation guarantee of 2.We generalize our algorithm to the Unsplittable Flow-Cover problem on a line, also for the setting of fractional items with non-linear costs. For this problem we obtain a (4+ε)-approximation algorithm in polynomial time, almost matching the 4-approximation algorithm known for the classical setting.
dc.description.funderANID Fondecyt Projecto No. 1181527
dc.fechaingreso.objetodigital2025-02-24
dc.format.extent15 páginas
dc.fuente.origenConveris
dc.identifier.doi10.4230/LIPIcs.ICALP.2020.46
dc.identifier.eisbn978-3-95977-138-2
dc.identifier.scopusidId: 2-s2.0-85089346460
dc.identifier.urihttps://doi.org/10.4230/LIPIcs.ICALP.2020.46
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/102221
dc.information.autorucEscuela de Ingeniería; Morales Bravo, Camilo Ignacio; S/I; 204029
dc.information.autorucEscuela de Ingeniería; Verschae Tannenbaum, José Claudio; 0000-0002-2049-6467; 243006
dc.language.isoen
dc.nota.accesocontenido completo
dc.publisherSchloss Dagstuhl, Leibniz-Zentrum für Informatik, GmbH
dc.relation.ispartofInternational Colloquium on Automata, Languages, and Programming (ICALP) : 47th : Saarbrücken, Germany (Virtual Conference)
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcs : 168
dc.rightsacceso abierto
dc.rights.licenseCC BY Attribution 3.0 Unported
dc.rights.urihttps://creativecommons.org/licenses/by/3.0/legalcode
dc.subjectKnapsack-Cover Inequalities
dc.subjectNon-Linear Knapsack-Cover
dc.subjectPrimal-Dual
dc.subjectWater-Filling Algorithm
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleA water filling primal dual algorithm for approximating non linear covering problems (2020)
dc.typecomunicación de congreso
sipa.codpersvinculados204029
sipa.codpersvinculados243006
sipa.trazabilidadConveris;20-07-2021
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIPIcs.ICALP.2020.46.pdf
Size:
490.42 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de conferencia