Bottleneck -link path
A DAG is called complete, if there are vertices , and is an edge if and only if . Let be the edge weights from to . The weight is called ordered, if and .
Find a path consists of edges from to , such that the maximum weight of the edges in the path is minimized.
One can formulate a dynamic programming algorithm, which takes time. My previous writing shows an time algorithm using the monge property. Using binary search, there is also an time algorithm if all weights are positive integers no larger than .
We show there is an time algorithm. Assume is the optimal weight. First, there is an oracle that given , decides if . Indeed, we can apply the greedy algorithm. Find the sequence , as follows. , is the largest value such that . If , then it is clear that . Also, we can show if , then . time seems to be a quite large bound. We could do it in instead by doing binary search for each . Using exponential search instead, we can obtain a time algorithm.
One need to do binary search for . There are weights, let it be . One does not have to know all of them in order to apply binary search. Note that is a matrix sorted in both row and column, hence we need a selection algorithm that returns the th smallest element for such matrix. There is an time algorithm for that. Hence we can do binary search on the sorted by spending time to access th element. We now obtain a 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 after all. We can do search for using oracle calls and time. Hence this gives us a time algorithm for the problem. Whenever , this is 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 contagious subarrays that minimizes the maximum sum of each subarray. It was an example for learning dynamic programming in chapter 8.5 of . An algorithm was given. Reading the discussion online, one would find time algorithm is the suggested solution, where 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 -link path problem because we can define to be the sum of elements from the th index of the array to the th index of the array. After preprocessing, can be computed in time. This results a running time algorithm.
 S.S. Skiena, The algorithm design manual, Springer, 2010.
 G.N. Frederickson, S. Zhou, Optimal parametric search for path and tree partitioning, CoRR. abs/1711.00599 (2017).