Techniques based on minimal graph cuts are well established as a standard tool for solving combinatorial optimization problems arising in image processing and computer vision applications. For binary pixel labeling problems these techniques can be used to minimize objective functions written as the sum of a set of unary and pairwise terms, provided that the objective function is submodular. This can be interpreted as minimizing the L1-norm of the vector containing all pairwise and unary terms. When the submodularity criterion is not fulfilled, however, the same optimization problem becomes NP-hard.

In this talk, we present some recent work on related optimization problems, where the L1-norm is exchanged for the L∞-norm (or max-norm). Remarkably, in this setting, the requirement that the pairwise terms must be submodular disappears, i.e., optimal solutions can be found in low order polynomial time regardless of the form of the unary and pairwise terms.