Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2p≥2 be an integer and TT be an edge-weighted tree. A cut on an edge of TT is a splitting of the edge at some point on it. A pp-edge-partition of TT is a set of pp subtrees induced by p−1p−1 cuts. Given pp and TT, the max–min continuous tree edge-partition problem is to find a pp-edge-partition that maximizes the length of the smallest subtree; and the min–max continuous tree edge-partition problem is to find a pp-edge-partition that minimizes the length of the largest subtree. In this paper, O(n2)O(n2)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer mm, a (non-ordered) set BB of nn non-negative real numbers, a real valued non-increasing function FF, and a real number tt, the problem is to find the largest number zz in {b/a|a∈[1,m],b∈B}{b/a|a∈[1,m],b∈B} such that F(z)≥tF(z)≥t. We give an O(n+tF×(logn+logm))O(n+tF×(logn+logm))-time algorithm for this problem, where tFtF is the time required to evaluate the function value F(z)F(z) for any real number zz.