On Computing the Nested Sums and Infimal Convolutions of Convex Piecewise-Linear Functions

Paul Tseng, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 languageEnglish (US)
Pages (from-to)240-266
Number of pages27
JournalJournal of Algorithms
Volume21
Issue number2
DOIs
StatePublished - 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.

Fingerprint Dive into the research topics of 'On Computing the Nested Sums and Infimal Convolutions of Convex Piecewise-Linear Functions'. Together they form a unique fingerprint.

Cite this