2-sided and multi-sided Stable Matchings: Structures, algorithms and applications

  • -

2-sided and multi-sided Stable Matchings: Structures, algorithms and applications

PhD Thesis Description

The title of the PhD Thesis of Dr. Pavlos Eirinakis is “2-sided and multi-sided Stable Matchings: Structures, algorithms and applications”. Its main contributions are summarized as follows: (1) A time-optimal algorithm for identifying all non-stable pairs that cannot be removed from the agents’ preference lists without affecting the set of solutions of the Stable Marriage (SM) problem. (2) Establishing several fundamental characteristics of the SM polytope; its dimension, its diameter and its minimal representation, i.e., it minimal equation system and its facets. (3) Establishing the dimension and the minimal representation of the rotation-based SM polytope. (4) The creation of time-optimal algorithms for finding all non-stable pairs in the Stable Admissions (SA) and the many-to-many Stable Matching (MM) problem. (5) A time- and space-optimal algorithm for identifying the set of solutions of the MM problem and a time-optimal algorithm for identifying a minimum-regret solution. (6) The design of a polynomial-time algorithm for finding the minimum weight solution for the MM problem; this algorithm also improves the (already known in the literature) bounds for finding the egalitarian and the “optimal” solution. (7) Providing the MM predicate, encoding the MM problem as a Constraint Satisfaction Problem and applying hyperarc consistency as a pre-processing step for solving similar problems using a Constraint Programming platform. (8) The extension of the notion of rotations (under specific conditions) in the context of Supply Chain Networks and chain stability and an algorithmic approach to such problems.

Phd Candidate

Pavlos Eirinakis

Ε-mail: peir[at]aueb[dot]gr
Office phone: +30 2108203663
Fax: +30 2108203664
Address: Evelpidon 47-A & Lefkados 33 Room 907, GR-11362, Athens, Greece

Supervisor

Dr. Yannis Mourtos