The Art Gallery Guardian

Bottleneck kk-link path


A DAG is called complete, if there are vertices v1,,vnv_1,\ldots,v_n, and vivjv_iv_j is an edge if and only if i<ji<j. Let w(i,j)w(i,j) be the edge weights from ii to jj. The weight is called ordered, if w(i,j)<w(i,j+1)w(i,j)<w(i,j+1) and w(i+1,j)<w(i,j)w(i+ 1,j)<w(i,j).

Problem1Bottleneck kk-link path problem

Find a path consists of kk edges from v1v_1 to vnv_n, such that the maximum weight of the edges in the path is minimized.

One can formulate a dynamic programming algorithm, which takes O(kn2)O(kn^2) time. My previous writing shows an O(kn)O(kn) time algorithm using the monge property. Using binary search, there is also an O(klog(n/k)logM)O(k\log(n/k)\log M) time algorithm if all weights are positive integers no larger than MM.

We show there is an O(n+klog(n/k)logn)O(n+k\log(n/k)\log n) time algorithm. Assume λ\lambda^* is the optimal weight. First, there is an oracle that given λ\lambda, decides if λλ\lambda\geq \lambda^*. Indeed, we can apply the greedy algorithm. Find the sequence a1,,aka_1,\ldots,a_k, as follows. a0=1a_0=1, aia_i is the largest value such that w(ai1,ai)λw(a_{i-1},a_i)\leq \lambda. If ak=na_k=n, then it is clear that λλ\lambda \geq \lambda^*. Also, we can show if ak<na_k<n, then λ<λ\lambda < \lambda^*. O(n)O(n) time seems to be a quite large bound. We could do it in O(klog(n))O(k\log (n)) instead by doing binary search for each aia_i. Using exponential search instead, we can obtain a O(klog(n/k))O(k\log(n/k)) time algorithm.

One need to do binary search for λ\lambda^*. There are Ω(n2)\Omega(n^2) weights, let it be WW. One does not have to know all of them in order to apply binary search. Note that ww is a matrix sorted in both row and column, hence we need a selection algorithm that returns the kkth smallest element for such matrix. There is an O(n)O(n) time algorithm for that. Hence we can do binary search on the sorted WW by spending O(n)O(n) time to access iith element. We now obtain a O((n+klog(n/k))logn)=O(nlogn)O((n+ k\log(n/k)) \log n) = O(n\log n) time algorithm. Not bad.

We can speed it up even further. Instead of selection in the sorted matrix, we can do search in the sorted matrix. We are given an oracle to test if a value is smaller than λ\lambda^* after all. We can do search for λ\lambda^* using O(logn)O(\log n) oracle calls and O(n)O(n) time. Hence this gives us a O(n+klog(n/k)logn)O(n+k\log (n/k) \log n) time algorithm for the problem. Whenever k=O(nlog(n)loglogn)k=O(\frac{n}{\log(n) \log \log n}), this is O(n)O(n) time.

As an application, we obtain a solution to Leetcode 410 Split Array Largest Sum. The problem is also called the linear partitioning problem. The problem asks one to partition array into kk contagious subarrays that minimizes the maximum sum of each subarray. It was an example for learning dynamic programming in chapter 8.5 of [1]. An O(kn2)O(kn^2) algorithm was given. Reading the discussion online, one would find O(nlogM)O(n\log M) time algorithm is the suggested solution, where MM is the maximum over all integers. The algorithm is actually fairly useful for photo galleries. There is the NPM package linear-partitioning, used by multiple photo galleries packages. My first encountered of the problem was also for photo gallery. The linear partition problem reduces to the bottleneck kk-link path problem because we can define w(i,j)w(i,j) to be the sum of elements from the iith index of the array to the jjth index of the array. After O(n)O(n) preprocessing, w(i,j)w(i,j) can be computed in O(1)O(1) time. This results a O(n+klog(n/k)logn)O(n+k\log (n/k) \log n) running time algorithm.

What about when kk is large? I’ve emailed Samson Zhou, who has confirmed the algorithm in [2] can be used to solve the problem in O(n)O(n) time.

References

[1] S.S. Skiena, The algorithm design manual, Springer, 2010.

[2] G.N. Frederickson, S. Zhou, Optimal parametric search for path and tree partitioning, CoRR. abs/1711.00599 (2017).

Posted by Chao Xu on .
Tags: algorithm, data structure.