Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time
Date Issued
2021
Author(s)
Abstract
Knapsack problems are among the most fundamental problems in optimization. In the Multiple Knapsack problem, we are given multiple knapsacks with different capacities and items with values and sizes. The task is to find a subset of items of maximum total value that can be packed into the knapsacks without exceeding the capacities. We investigate this problem and special cases thereof in the context of dynamic algorithms and design data structures that efficiently maintain near-optimal knapsack solutions for dynamically changing input. More precisely, we handle the arrival and departure of individual items or knapsacks during the execution of the algorithm with worst-case update time polylogarithmic in the number of items. As the optimal and any approximate solution may change drastically, we maintain implicit solutions and support polylogarithmic time query operations that can return the computed solution value and the packing of any given item.
While dynamic algorithms are well-studied in the context of graph problems, there is hardly any work on packing problems (and generally much less on non-graph problems). Motivated by the theoretical interest in knapsack problems and their practical relevance, our work bridges this gap.
While dynamic algorithms are well-studied in the context of graph problems, there is hardly any work on packing problems (and generally much less on non-graph problems). Motivated by the theoretical interest in knapsack problems and their practical relevance, our work bridges this gap.
Subjects
Fully dynamic algorithms
;
knapsack problem
;
approximation schemes
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Institution
Type
conference paper
Journal/Edited collection
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) = Leibniz International Proceedings in Informatics (LIPIcs), Band 213
Start page
18:1
End page
18:17
Secondary publication
Yes
Document version
Published Version
Language
English
File(s)![Thumbnail Image]()
Loading...
Name
Eberle et al_Fully Dynamic Algorithms for Knapsack Problems_2021_published-version.pdf
Size
789.96 KB
Format
Adobe PDF
Checksum
(MD5):02b6ea80ebf0cc7de2e89361262585ed