IPEC Nerode Prize 2017 - Nomination

The EATCS-IPEC Nerode Prize 2017 for outstanding papers in the area of multivariate algorithmics is awarded to

Fedor V. Fomin (University of Bergen, Norway) Fabrizio Grandoni (IDSIA, University of Lugano, Switzerland) and Dieter Kratsch (Université de Lorraine - Metz, France)

for their paper

A Measure & Conquer Approach for the Analysis of Exact Algorithms Journal of the ACM 65 (5): Article 25, 2009.

Appraisal

Branch-and-reduce backtracking and its variations have become one of the most commonly used tools for solving hard optimization problems. It is useful both in practice as well as in theory. Prior to the work of Fomin, Grandoni and Kratsch a typical way to improve over the state of the art was to extend a backtracking algorithm with a deepened case distinction, resulting in overcomplicated algorithms, unlikely to be ever implemented. The "measure and conquer" method brought a revolution. Instead of analyzing the complexity of multiple levels of branching, the technique assigns a carefully designed measure based on the elements and structural features of each instance and an assignment of weights to those features. This allows backtracking algorithms to be analyzed using simple recurrence relations, and the weights for this analysis to be chosen using mathematical optimization.

This method results in intuitive, elegant and simple algorithms. The technique shifts complexity of the problem from algorithm design to the analysis, which can then often be automated. The analysis based on measure and conquer is inherently multivariate. This method has led to new upper bounds on the complexity of numerous fundamental NP-complete problems including set cover, dominating set, feedback vertex set, and independent set, with algorithms that are simpler than previous methods for the same problems. These upper bounds are obtained with respect to various parameterizations of these problems such as the number of vertices in the input graph, the solution size and the structural parameters. Soon after its introduction the area exploded with numerous results applying measure and conquer.

Measure and conquer unified and generalized earlier attempts to formalize the analysis of backtracking algorithms. It improved our understanding of the branch-and-reduce backtracking process, provided an easy to use framework, and opened new perspectives for development of practically feasible algorithms for solving hard computational problems.

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.