AarXiv2021

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

Cornelius Brand, Martin Koutecký, Alexandra Lassota, Sebastian Ordyniak

Abstract

'Sebastian Ordyniak'] 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 exhibit two fundamental classes of mixed integer (linear) programs that run counter this intuition. Namely those whose constraint matrices have small coefficients and small primal or dual treedepth: While linear optimization is easy [Brand, Kouteck´y, Ordyniak, AAAI 2021], we prove that separable convex optimization is much harder. Moreover, in the pure integer and mixed integer linear cases, these two classes have the same parameterized complexity. We show that they yet behave quite differently in the separable convex mixed integer case.

A figure from Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

Convex separable optimization can be far harder than linear optimization for certain small‑coefficient, low‑treedepth mixed‑integer programs.

What’s new

i.Identify two fundamental classes of mixed‑integer programs with small coefficients and small primal or dual treedepth where convex separable optimization is much harder than linear optimization
ii.Prove parameterized hardness of separable convex optimization for these classes, contrasting with known linear‑optimization easiness
iii.Derive the first non‑trivial lower and upper bounds on the norm of mixed Graver basis elements
iv.Show that these bounds do not lead to efficient algorithms and formally rule out such algorithms

How they did it

The authors employ the mixed Graver basis framework introduced by Hemmecke, deriving novel lower and upper bounds on the norm of its elements, and conduct a parameterized complexity analysis to establish hardness results for convex separable optimization in the identified classes.

What they found

Established lower and upper bounds on the norm of mixed Graver basis elements (first non‑trivial bounds)
Proved that separable convex optimization is parameterized‑hard for matrices with small coefficients and small treedepth, unlike the linear case

Caveats

✕Results apply only to mixed‑integer programs with small coefficients and bounded primal or dual treedepth
✕Upper bounds on mixed Graver basis norms do not yield efficient algorithms for the convex case

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

Searching the other archives…