LiftMatch (771136)

  https://cordis.europa.eu/project/id/771136

  Horizon 2020 (2014-2020)

  Lifting Methods for Global Matching Problems

  ERC Consolidator Grant (ERC-2017-COG)

 

  2018-03-01 Start Date (YY-MM-DD)

  2023-02-28 End Date (YY-MM-DD)

  € 1,675,640 Total Cost

  Description

"This proposal presents a research program aimed at breaking new ground in theoretical, algorithmic and practical aspects of the notoriously difficult matching problems. The main goal is developing a unified algorithmic framework for matching problems that enjoys theoretical guarantees and high practical value for ``real-life'' applications. The core methodological aspect is the modelling of matching problems as high-dimensional, lifted convex problems that can be efficiently approximated. We present several case-studies of this methodology, constructing efficient algorithms for approximating the solutions of important instances of the matching problem. The results already demonstrate state of the art performance and are backed-up with novel theoretical analysis proving tightness and correctness of the suggested convexifications for certain classes of non-trivial input. This proposal has ``high risk - high impact'' profile: The ``high-risk"" aspect of this proposal comes from the hardness of general matching problems which, when faithfully represented, are NP-hard. However, as we demonstrate, combining convex optimization tools in a careful way, that takes into account computational complexity, is likely to push forward the limits of current algorithmic solutions. The ``High-impact"" will be immediate: As matching problems exist in almost every aspect of scientific research, practical generic algorithms for matching problems are likely to have a significant influence. We believe that the inroads and preliminary results presented in this proposal already provide strong evidence for the potential success of the suggested research program."

  Complicit Organisations

1 Israeli organisation participates in LiftMatch.