Dorit S. Hochbaum - 2011 ICS prize for Research excellence in the Interface Between Operations Research and Computer Science

2011 INFORMS Computing Society (ICS) Prize for

Research Excellence in the Interface

Between Operations Research and Computer Science

Recipient: Dorit S. Hochbaum



Winning Paper

Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 32, no. 5, pp 889-898, 2010 (download paper, here).


This paper presents an efficient, highly novel approach for solving a group of well-known combinatorial optimization problems arising in computer vision and image analysis, including the ratio-regions problem and a variant of the normalized-cut problem. Each problem expresses two conflicting objectives by a single nonlinear, ratio objective. Such conflicting objective could be, for example, the desire to cluster similar pixels together while limiting the total number of clusters.  Although studied for over a decade, researchers have suspected these problems to be NP-hard and hence have proposed approximate, continuous-based algorithms for their solution.

The author recast each problem as a single-parameter parametric integer program with monotone inequality constraints. For a fixed parameter, this integer problem can in turn be solved as a minimum-cut problem. Fortunately there are just a linear number of parameter break points to evaluate, and so the overall algorithm is fast in theory and effective in practice. In addition, the parametric approach provides information on the trade-off between the two conflicting objectives.  Besides solving these specific problems, this paper also sheds light on the difficulty of other related NP-hard problems.

In short, this paper provides a beautiful contribution to computer vision by taking a very innovative angle and demonstrating how to derive algorithms with strong performance guarantees and excellent experimental behavior.

What is ICS Prize?

The INFORMS Computing Society (ICS) Prize is an annual award for the best English language paper or group of related papers dealing with the Operations Research/Computer Science interface. The award is accompanied by a certificate and a $1,000 honorarium. 

For more information, click here.

For more information see ICS 2012 Newletter (page 4).

Link to Dorit S. Hochbaum's website.