most recent 30 from http://mathoverflow.net 2013-05-19T20:07:37Z http://mathoverflow.net/feeds/question/76075 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76075/number-of-breakpoints-in-parametric-maximum-flow-problems Ben 2011-09-21T19:37:03Z 2011-09-21T19:37:03Z

<p>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}&lt;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.</p> <p>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.</p>