Algorithms for Locating Constrained Optimal Intervals

Simple item page
dc.creatorLiu, Hsiao-Fei
dc.creatorChen, Peng-An
dc.creatorChao, Kun-Mao
dc.date2008-09-11
dc.date.accessioned2026-07-07T10:02:29Z
dc.date.available2026-07-07T10:02:29Z
dc.descriptionIn 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 \geq 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\leq L_s\leq 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 \geq L_s$, where $T(n')$ is the time required to solve the all-pairs shortest paths problem on a graph of $n'$ nodes. By the latest result of Chan \cite{Chan}, $T(n')=O(n'^3 \frac{(\log\log n')^3}{(\log n')^2})$, so our algorithm runs in subquadratic time $O(nL_s\frac{(\log\log L_s)^3}{(\log L_s)^2})$.
dc.descriptionAn earlier version of the second part of this work appeared in Proceedings of the 18th International Symposium on Algorithms and Computation, Japan, 2007
dc.identifierhttps://arxiv.org/abs/0809.2097
dc.identifierhttp://arxiv.org/abs/0809.2097
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168988
dc.subjectData Structures and Algorithms
dc.titleAlgorithms for Locating Constrained Optimal Intervals
dc.typetext

Files

Collections

arXiv