License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.19
URN: urn:nbn:de:0030-drops-105952
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10595/
Axiotis, Kyriakos ;
Tzamos, Christos
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
Abstract
One of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(T n). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger, 1999]. In comparison, our algorithm implies a bound of O(n M^2) without any dependence on V, or O(n V^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Marek Cygan et al., 2017; Marvin Künnemann et al., 2017].
We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(k m), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider.
BibTeX - Entry
@InProceedings{axiotis_et_al:LIPIcs:2019:10595,
author = {Kyriakos Axiotis and Christos Tzamos},
title = {{Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {19:1--19:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10595},
URN = {urn:nbn:de:0030-drops-105952},
doi = {10.4230/LIPIcs.ICALP.2019.19},
annote = {Keywords: Knapsack, Fine-Grained Complexity, Dynamic Programming}
}
|
Keywords: |
|
Knapsack, Fine-Grained Complexity, Dynamic Programming |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
