Algorithmic and structural aspects of stable matching problems

  • -

Algorithmic and structural aspects of stable matching problems


Full Title: Algorithmic and structural aspects of stable matching problemsCall: Slovak-Greece Research and Development Cooperation

Project Duration: 2 Years

Project Start: 2013

Project End: 2015

Website: (under construction)

Short Summary: The aim of this project is to study various variants of matching problems from their computational as well as structural perspective. The basic matching model consists of a finite set of participants who wish to collaborate in some sense, each having different criteria of desirability. Such models are intensively studied in various branches of economics, like computational social choice, auction theory, general equilibrium theory, game theory etc.  Since the variability of the real systems is very rich, new modifications of existing models emerge, bringing forward new tasks for researchers. The intention is to explore algorithmic questions connected with the following problems: decision about the existence of the solution, finding an optimal solution, describing the structure of all solutions etc. The overall aim is to propose an efficient algorithm or to prove the intractability of the studied problem. In case of NP-complete problems their approximability and parameterized complexity will be studied.  In describing the structural properties, the basic tools used will be graph theory, polyhedral combinatorics, combinatorial optimization, matroid theory and various techniques of the computational complexity theory