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

✍ Scribed by Paul Tseng; Zhi-Quan Luo

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 250 KB
• Volume: 21
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0045

✦ Synopsis

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 Ž 2 . general case, we give an O N log N time algorithm. We apply this latter algorithm to the linear cost network flow problem on series-parallel networks to Ž

2

. obtain an O m log 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 q m log m , where n is the number of nodes.