Document Open Access Logo

On the Fine-Grained Complexity of One-Dimensional Dynamic Programming

Authors Marvin Künnemann, Ramamohan Paturi, Stefan Schneider

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.21.pdf
  • Filesize: 0.59 MB
  • 15 pages

Document Identifiers

Author Details

Marvin Künnemann
Ramamohan Paturi
Stefan Schneider

Cite As Get BibTex

Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.21

Abstract

In this paper, we investigate the complexity of one-dimensional dynamic programming, or more specifically, of the Least-Weight 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 near-linear time algorithms   for some specific special cases, little is known about when an LWS instantiation admits a subquadratic-time 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 fine-grained 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 low-rank 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 SETH-hardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the (min,+)-convolution-hardness of the knapsack problem. Furthermore, we revisit some of the LWS instantiations which are known to be solvable in near-linear time   and explain their easiness in terms of the easiness of the corresponding core problems.

Subject Classification

Keywords
  • Least-Weight Subsequence
  • SETH
  • Fine-Grained Complexity
  • Knapsack
  • Subquadratic Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness of LCS and other sequence similarity measures. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15), pages 59-78, 2015. Google Scholar
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with Edit Distance and friends or: A polylog shaved is a lower bound made. In Proc. 48th Annual ACM Symposium on Symposium on Theory of Computing (STOC'16), 2016. To appear. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP'14), pages 39-51, 2014. Google Scholar
  4. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 218-230, 2015. Google Scholar
  5. Alfred V. Aho, Daniel S. Hirschberg, and Jeffrey D. Ullman. Bounds on the complexity of the longest common subsequence problem. Journal of the ACM, 23(1):1-12, 1976. URL: http://dx.doi.org/10.1145/321921.321922.
  6. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. 47th Annual ACM Symposium on Theory of Computing (STOC'15), pages 51-58, 2015. URL: http://dx.doi.org/10.1145/2746539.2746612.
  7. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9734-3.
  8. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS'14), pages 661-670, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.76.
  9. Karl Bringmann. A near-linear pseudopolynomial time algorithm for Subset Sum. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 1073-1084, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.69.
  10. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and Dynamic Time Warping. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS'15), pages 79-97, 2015. Google Scholar
  11. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. In Proc. 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS'16), pages 261-270, 2016. URL: http://dx.doi.org/10.1145/2840728.2840746.
  12. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via additive combinatorics. In Proc. 47th Annual ACM Symposium on Theory of Computing, (STOC'15), pages 31-40, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
  13. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min,+)-convolution. ArXiv e-prints, February 2017. URL: http://arxiv.org/abs/1702.07669.
  14. Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants. In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP'16), pages 5:1-5:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.5.
  15. David Eppstein. Sequence comparison with mixed convex and concave costs. J. Algorithms, 11(1):85-101, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90031-9.
  16. David A. Eppstein. Efficient algorithms for sequence analysis with concave and convex gap costs. PhD thesis, Columbia University, 1989. Google Scholar
  17. Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. URL: http://dx.doi.org/10.1016/0012-365X(75)90103-X.
  18. Anka Gajentaan and Mark H Overmars. On a class of O(n²) problems in computational geometry. Computational geometry, 5(3):165-185, 1995. Google Scholar
  19. Zvi Galil and Raffaele Giancarlo. Speeding up dynamic programming with applications to molecular biology. Theoretical Computer Science, 64(1):107-118, 1989. URL: http://dx.doi.org/10.1016/0304-3975(89)90101-1.
  20. Zvi Galil and Kunsoo Park. A linear-time algorithm for concave one-dimensional dynamic programming. Inf. Process. Lett., 33(6):309-311, 1990. URL: http://dx.doi.org/10.1016/0020-0190(90)90215-J.
  21. Zvi Galil and Kunsoo Park. Parallel algorithms for dynamic programming recurrences with more than O(1) dependency. J. Parallel Distrib. Comput., 21(2):213-222, 1994. URL: http://dx.doi.org/10.1006/jpdc.1994.1053.
  22. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 2162-2181, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.141.
  23. Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, and Mingzhou Song. Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. ArXiv e-prints, January 2017. URL: http://arxiv.org/abs/1701.07204.
  24. Daniel S. Hirschberg and Lawrence L. Larmore. The least weight subsequence problem. SIAM Journal on Computing, 16(4):628-638, 1987. URL: http://dx.doi.org/10.1137/0216043.
  25. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, and Stefan Schneider. 0-1 Integer Linear Programming with a linear number of constraints. ArXiv e-prints, January 2014. URL: http://arxiv.org/abs/1401.5512.
  26. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  27. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  28. Alon Itai, Christos H Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676-686, 1982. Google Scholar
  29. Maria M. Klawe and Daniel J. Kleitman. An almost linear time algorithm for generalized matrix searching. SIAM J. Discrete Math., 3(1):81-97, 1990. URL: http://dx.doi.org/10.1137/0403009.
  30. Donald E. Knuth and Michael F. Plass. Breaking paragraphs into lines. Softw., Pract. Exper., 11(11):1119-1184, 1981. URL: http://dx.doi.org/10.1002/spe.4380111102.
  31. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-grained Complexity of One-Dimensional Dynamic Programming. ArXiv e-prints, March 2017. URL: http://arxiv.org/abs/1703.00941.
  32. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. Google Scholar
  33. William J. Masek and Mike Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90002-1.
  34. Jiří Matoušek. Efficient partition trees. Discrete &Computational Geometry, 8(1):315-334, 1992. Google Scholar
  35. Webb Miller and Eugene W. Myers. Sequence comparison with concave weighting functions. Bulletin of Mathematical Biology, 50(2):97-120, 1988. URL: http://dx.doi.org/10.1007/BF02459948.
  36. David Pisinger. Dynamic programming on the word RAM. Algorithmica, 35(2):128-145, 2003. URL: http://dx.doi.org/10.1007/s00453-002-0989-y.
  37. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis (invited talk). In Proc. 10th International Symposium on Parameterized and Exact Computation (IPEC'15), pages 17-29, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.17.
  38. Robert E. Wilber. The concave least-weight subsequence problem revisited. J. Algorithms, 9(3):418-425, 1988. URL: http://dx.doi.org/10.1016/0196-6774(88)90032-6.
  39. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. Google Scholar
  40. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS'10), pages 645-654, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  41. F. Frances Yao. Efficient dynamic programming using quadrangle inequalities. In Proc. 12th Annual ACM Symposium on Theory of Computing (STOC'80), pages 429-435, 1980. URL: http://dx.doi.org/10.1145/800141.804691.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact