Abstract
In this paper, we investigate the complexity of onedimensional dynamic programming, or more specifically, of the LeastWeight Subsequence (LWS) problem: Given a sequence of n data items together with weights for every pair of the items, the task is to determine a subsequence S minimizing the total weight of the pairs adjacent in S. A large number of natural problems can be formulated as LWS problems, yielding obvious O(n^2)time solutions.
In many interesting instances, the O(n^2)many weights can be succinctly represented. Yet except for nearlinear time algorithms for some specific special cases, little is known about when an LWS instantiation admits a subquadratictime algorithm and when it does not. In particular, no lower bounds for LWS instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the finegrained complexity of succinct instantiations of the LWS problem: Given an LWS instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be.
More specifically, we prove subquadratic equivalences between the following pairs (an LWS instantiation and the corresponding core problem) of problems: a lowrank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)convolution. Using these equivalences and known SETHhardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the (min,+)convolutionhardness of the knapsack problem. Furthermore, we revisit some of the LWS instantiations which are known to be solvable in nearlinear time and explain their easiness in terms of the easiness of the corresponding core problems.
BibTeX  Entry
@InProceedings{knnemann_et_al:LIPIcs:2017:7468,
author = {Marvin K{\"u}nnemann and Ramamohan Paturi and Stefan Schneider},
title = {{On the FineGrained Complexity of OneDimensional Dynamic Programming}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7468},
URN = {urn:nbn:de:0030drops74688},
doi = {10.4230/LIPIcs.ICALP.2017.21},
annote = {Keywords: LeastWeight Subsequence, SETH, FineGrained Complexity, Knapsack, Subquadratic Algorithms}
}
Keywords: 

LeastWeight Subsequence, SETH, FineGrained Complexity, Knapsack, Subquadratic Algorithms 
Collection: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) 
Issue Date: 

2017 
Date of publication: 

07.07.2017 