Algorithms for Locating Constrained Optimal Intervals

Abstract

In this work, we obtain the following new results. 1. Given a sequence $D=((h_1,s_1),(h_2,s_2)...,(h_n,s_n))$ of number pairs, where $s_i>0$ for all $i$, and a number $L_h$, we propose an O(n)-time algorithm for finding an index interval $[i,j]$ that maximizes $\frac{{\sum }_{k=i}^j{h}_k}{{\sum }_{k=i}^j{s}_k}$ subject to ${\sum }_{k=i}^j{h}_k\ge L_h$. 2. Given a sequence $D=((h_1,s_1),(h_2,s_2)...,(h_n,s_n))$ of number pairs, where $s_i=1$ for all $i$, and an integer $L_s$ with $1\le L_s\le n$, we propose an $O(n\frac{T(L_s^{1/2})}{L_s^{1/2}})$-time algorithm for finding an index interval $[i,j]$ that maximizes $\frac{{\sum }_{k=i}^j{h}_k}{\sqrt{{\sum }_{k=i}^j{s}_k}}$ subject to ${\sum }_{k=i}^j{s}_k\ge L_s$, where $T(n^{\prime })$ is the time required to solve the all-pairs shortest paths problem on a graph of $n^{\prime }$ nodes. By the latest result of Chan \cite{Chan}, $T(n^{\prime })=O(n^{\prime 3}\frac{(\log \log n^{\prime }{)}^3}{(\log n^{\prime }{)}^2})$, so our algorithm runs in subquadratic time $O(n{L}_s\frac{(\log \log L_s{)}^3}{(\log L_s{)}^2})$.

An earlier version of the second part of this work appeared in Proceedings of the 18th International Symposium on Algorithms and Computation, Japan, 2007