2011 ICS Prize Winner
The 2011 ICS Prize was awarded to Dorit Hochbaum for her 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).
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.
2011 ICS Prize Committee:
- Sam Burer (chair)
- David Kelton
- Pascal Van Hentenryck
2010 ICS Prize Winners
The 2010 ICS Prize was awarded to Jesús A. De Loera, Jon Lee, Peter N. Malkin, Susan Margulies, and Shmuel Onn for their papers:
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation (ISSAC 2008, Linz/Hagenberg, Austria), Association for Computing Machinery, (2008), 197-206,
- Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz Combinatorics, Probability and Computing, Volume 18, Issue 04, (2009), 551-582.
These two papers introduce a pioneering new approach for proving the optimality of solutions to combinatorial optimization problems. The approach begins by encoding the instance and an objective bound as a system of polynomial equations over a finite field. Then, using Hilbert's Nullstellensatz, the authors demonstrate the effectiveness of a computational method to certify the infeasibility of the polynomial system. The encoding is derived and analyzed for a number of problem classes, such as the k-coloring, stable set, longest cycle, largest planar subgraph, and minimum edge coloring problems. While the degree of the certifying polynomial could be exponentially large, the authors demonstrate that in many cases of interest the degree is low enough to allow for explicit, fast computations. The authors also develop a variety of computational enhancements, including computing over finite fields, exploiting symmetry, adding redundant equations, and applying alternative Nullstellensätze that allow them to solve 3-coloring problems significantly faster than existing methods.
In this impressive work, the authors take up a mathematical machinery that seemed very unlikely to be useful in practice and turn it into a useful computational algorithm. This work is likely to stimulate additional research into computational polynomial methods, perhaps placing them on the same footing as polyhedral techniques for solving combinatorial optimization problems.
2010 ICS Prize Committee:
- Karen Aardal
- Sam Burer
- Jeff Linderoth
- Andreas Waechter (chair)
2009 ICS Prize Winners
The 2009 ICS Prize was awarded to Andreas Waechter and Lorenz Biegler for their paper, "An Interior-Point Filter line-Search Algorithm for Large-Scale Nonlinear Programming" (Mathematical Programming 106(1), pp. 25--57, 2006).
Abstract: We present an algorithm for large-scale nonlinear continuous optimization, together with real-life applications, such as the tuning of transistors in digital circuits, modeling and design of chemical processes and optimal control of nonlinear dynamic systems. We will also present some recent developments of the algorithm, including parametric sensitivity of NLP solutions and the use of iterative linear solvers. An implementation of this algorithm ("Ipopt") is available as open source.
2009 ICS Prize Committee:
- S. Raghavan (Chair)
- Karen Aardal
- Michael Trick
- Stefan Voss
2008 ICS Prize Winners
The 2008 ICS Prize was awarded to Robert W. Day and S. Raghavan for their paper, "Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions" [Management Science 53:9 (2007), 1389–1406].
This paper presents a new practical approach for combinatorial auctions, auctions in which bidders specify bids on bundles of items rather than on individual items. Combinatorial auctions have been applied when the value of a bundle of goods to a bidder is not merely the sum of the values of the individual items, such as in airplane slot allocations and spectrum allocations.
There is no universally agreed-upon method for determining the allocation of goods to bidders in combinatorial auctions, thus limiting their practical use. The Day-Raghavan paper developed an approach for determining winners of the auction as well as payments that satisfy two important properties:
- the payment method is incentive-compatible for bidders to bid their true values for bundles of goods, thus avoiding a need for extensive knowledge of the bidding of their competitors, and avoiding substantial underbidding.
- the payments are in the core; that is, there is no coalition of bidders that would be willing to pay more for any bundle of goods than the prices charged to the winning bidders.
This paper overcomes some key weaknesses Vickrey-Clarke-Groves (VCG) auction mechanism, which is an alternative mechanism that is compatible with bidders bidding their true values. First, the VCG mechanism can result in very low payments, thus making auctions impractical. Second, the VCG mechanism can result in payments that are not in the core, which would be perceived as unfair by any coalition who has bid more on items than they are sold for.
The authors present a model that achieves the two properties given above. They also provide a practical solution approach, using column generation, for finding pareto-optimal solutions. Their approach is practical for governmental combinatorial auctions and has already been used in the United Kingdom in auctions for allocating spectrum.
2007 ICS Prize Winners
The 2007 ICS Prize was awarded to J. Csirik, D. S. Johnson, C. Kenyon, J.B. Orlin, P.W. Shor, and R.R. Weber.