Given a sequence of n numbers, the MAXIMUM CONSECUTIVE SUBSUMS PROBLEM (MCSP) asks for the maximum consecutive sum of lengths ℓ for each ℓ = 1, ..., n. No algorithm is known for this problem which is significantly better than the naive quadratic solution. Nor a super linear lower bound is known. The best known bound for the MCSP is based on the the computation of the (min; +)-convolution, another problem for which neither an O(n2-ε) upper bound is known nor a super linear lower bound. We show that the two problems are in fact computationally equivalent by providing linear reductions between them. Then, we concentrate on the problem of finding super linear lower bounds and provide empirical evidence for our conjecture that the solution of both problems requires Ω(n log n) time in the decision tree model.
On lower bounds for the Maximum Consecutive Subsums Problem and the (min, +)-convolution
Cicalese, Ferdinando
2014-01-01
Abstract
Given a sequence of n numbers, the MAXIMUM CONSECUTIVE SUBSUMS PROBLEM (MCSP) asks for the maximum consecutive sum of lengths ℓ for each ℓ = 1, ..., n. No algorithm is known for this problem which is significantly better than the naive quadratic solution. Nor a super linear lower bound is known. The best known bound for the MCSP is based on the the computation of the (min; +)-convolution, another problem for which neither an O(n2-ε) upper bound is known nor a super linear lower bound. We show that the two problems are in fact computationally equivalent by providing linear reductions between them. Then, we concentrate on the problem of finding super linear lower bounds and provide empirical evidence for our conjecture that the solution of both problems requires Ω(n log n) time in the decision tree model.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
