Abstract
We consider the problem of evaluating a functional expression comprising the nested sums and infimal convolutions of convex piecewise-linear functions defined on the reals. For the special case where the nesting is serial, we give an O(N log N) time algorithm, where N is the total number of breakpoints of the functions. We also prove a lower bound of Ω(N log N) on the number of comparisons needed to solve this problem, thus showing that our algorithm is essentially optimal. For the general case, we give an O(N log2 N) time algorithm. We apply this latter algorithm to the linear cost network flow problem on series-parallel networks to obtain an O(m log2 m) time algorithm for this problem, where m is the number of arcs in the network. This result improves upon the previous algorithm of Bein, Brucker, and Tamir which has a time complexity of O(nm + m log m), where n is the number of nodes.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 240-266 |
| Number of pages | 27 |
| Journal | Journal of Algorithms |
| Volume | 21 |
| Issue number | 2 |
| DOIs | |
| State | Published - Sep 1996 |
Bibliographical note
Funding Information:* This research was partially supported by the U.S. Army Research Office, Contract DAAL03-86-K-0171 Center for Intelligent Control Systems), and by a grant from the Science and Engineering Research Board of McMaster University. ²E-mail: tseng@math.washington.edu. ³E-mail: luozq@mcmail.cis.mcmaster.ca.