A strongly polynomial preprocessing for quadratic binary optimization

Endre Boros
Rutgers University

Merging several earlier results we propose a network flow based preprocessing algorithm aiming at simplifying and decomposing a quadratic unconstrained minimization problem in polynomial time. We can demonstrate on numerous applications, including MRI image processing that this method in fact is able to find the optimal solution (not only simplify it) of many large real life problems.

*Joint work with Peter L. Hammer and Gabriel Tavares

Presentation (PDF File)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems