2026-08-16T22:40:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4688 2024-03-06T10:35:14Z ddc:004 open_access

Online Set Cover with Set Requests Bhawalkar, Kshipra Gollapudi, Sreenivas Panigrahi, Debmalya Online Algorithms Set Cover We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kshipra Bhawalkar and Sreenivas Gollapudi and Debmalya Panigrahi 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.64 urn:nbn:de:0030-drops-46883 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.64 eng https://creativecommons.org/licenses/by/3.0/legalcode