Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$ where all $c_{ij}<0$ (so that the function can be evaluated in polynomial time). $f$ will be piecewise affine and the number of breakpoints can in general be exponential in the size of $x$. The example of this uses a similar construction as in the proof that the simplex method can require an exponential number of steps.

But what if we impose some other restrictions? For example, many graphs occuring in e.g. computer vision have a limited number of connections between the variables. That is, for any $i$, the number of $c_{ij}\neq 0$ is less than or equal to $K$. Can we then prove that the number of breakpoints of $f$ will be polynomially bounded, e.g. less than $p(n)2^K$? This would be interesting to the field of computer vision, where these problems appear.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.