48 citations · 61 across the 5 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017★ 4 cited
On the Fine-grained Complexity of One-Dimensional Dynamic Programming
Marvin Künnemann, Ramamohan Paturi, Stefan Schneider
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 da…
cs.DS2017★ 48 cited
Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen +3
The -Means clustering problem on points is NP-Hard for any dimension , however, for the 1D case there exists exact polynomial time algorithms. Previous literature re…