Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises

Cornelius Brand, Martin Koutecký, Alexandra Lassota +1

An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibi…