2026-07-20T14:42:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26247 2026-06-24T05:03:52Z ddc:004 open_access

Online Algorithms for Set Packing with Renewable Capacities Chaturvedi, Anya Moses Jr., William K. Scheideler, Christian Wong, Prudence W. H. Set packing online algorithms learning-augmented algorithms We propose and study a new extension of the classical set packing problem, which we call the online D-set packing with renewable capacities (D-SPaRC) problem. In the D-SPaRC setting, there is a collection of resources with associated capacities. Requests arrive one by one, and for each request, a decision has to be made to accept it or not before seeing future requests. Each request is associated with a collection of subsets of resources, with each subset having cardinality at most D. When accepting a request, exactly one of these subsets must be chosen, which consumes one unit of capacity on each of the involved resources. Over time, the available resource capacities may be renewed, allowing additional requests to be accepted. Many online problems, including packing, routing, and scheduling, can be formulated as a D-SPaRC problem, thus underlining its usefulness. We first present a simple greedy algorithm that is O(ĉ_min ⋅ (D^{1/ĉ_min}-1))-competitive for D ≥ 2 and 3-competitive if D = 1, where ĉ_min is the minimum capacity of the resources. We then show that, for ĉ_min = Ω(log D), the greedy algorithm can be extended to an online algorithm with predictions whose competitive ratio is never worse than that of the original greedy approach and can, in fact, be reduced to a constant when the predictions are optimal. Finally, we generalize the D-SPaRC problem in two meaningful ways, namely by addressing non-uniform request priorities and by handling requests with non-uniform weights. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anya Chaturvedi and William K. Moses Jr. and Christian Scheideler and Prudence W. H. Wong 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.13 urn:nbn:de:0030-drops-262472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode