Highlights
IDSIA's Fabrizio Grandoni wins the Nerode Prize
18 September 2017
Fabrizio Grandoni of IDSIA has been awarded the EATCS-IPEC Nerode Prize 2017 for outstanding papers in the area of multivariate algorithmics together with Fedor V. Fomin (University of Bergen, Norway) 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 the most
commonly used tool for solving hard optimization problems. 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. 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. 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.

The Award Committee:
Jianer Chen (Texas A&M University, USA)
David Eppstein (University of California, Irvine, USA, chair)
Daniel Marx (Hungarian Academy of Sciences)

 

st.wwwsupsi@supsi.ch