2026-07-21T20:02:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12453 2024-03-06T10:50:10Z ddc:004 open_access

A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems Fielbaum, Andrés Morales, Ignacio Verschae, José Knapsack-Cover Inequalities Non-Linear Knapsack-Cover Primal-Dual Water-Filling Algorithm Obtaining 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrés Fielbaum and Ignacio Morales and José Verschae 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.46 urn:nbn:de:0030-drops-124531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.46 eng https://creativecommons.org/licenses/by/3.0/legalcode