Name
Title | ||
|---|---|---|
On lower bounds for the Maximum Consecutive Subsums Problem and the (min,+)-convolution |
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ISIT.2014.6875145 | Information Theory |
Keywords | Field | DocType |
convolution,decision trees,(min,+)-convolution,decision tree model,maximum consecutive subsums problem,super linear lower bound | Discrete mathematics,Decision tree,Combinatorics,Upper and lower bounds,Computer science,Convolution,Quadratic equation,Decision tree model,Conjecture,Computation | Conference |
Citations | PageRank | References |
2 | 0.40 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Sany Laber | 1 | 229 | 27.12 |
| Wilfredo Bardales R. | 2 | 2 | 0.40 |
| Ferdinando Cicalese | 3 | 450 | 48.20 |
| Bardales R, W. | 4 | 2 | 0.40 |