Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

On matchings and related problems in graphs, hypergraphs, and doubly stochastic matrices

ven 09 oct 2020



Soutenance de M. Ioannis PANAGIOTAS sous la direction de M. Bora UCAR

Langue(s) des interventions

Description générale

This thesis investigates four dierent matching-related problems that arise in the area of Combinatorial Scientific Computing. The thesis is supervised by Bora Uçar and co-directed by Fanny Dufossé.
The first problem is that of finding a maximum cardinality matching in graphs efficiently. There already exist exact, polynomial time algorithms for this purpose. We focused on creating fast (linear or near-linear) probabilistic heuristics and approximation algorithms which can find a large matching, often very close in cardinality to the optimal. Such algorithms are used to initialize exact algorithms and can massively improve their performance. For the majority of our results in this part, we based the random decisions of the algorithms on the doubly stochastic matrix that occurs by scaling the adjacency matrix of the graphs. We investigated the problem on the class of bipartite graphs (where odd cycles are not allowed) as well as general graphs. The proposed algorithms obtain matchings with larger cardinality than other widely used methods while having the same or reduced run time. They also yield reduced run times for the exact algorithms.The second investigated problem concerns the maximum cardinality matching in d-partite, d-uniform graphs, which are extensions of bipartite graphs in higher dimensions. The examined problem is NP-Hard and we proposed a series of heuristics.
These heuristics range from generalizations of existing heuristics for the bipartite case, to new ones utilizing scaling methods. The proposed heuristics obtain matchings with large cardinality on a collection of random, synthetic, and real datasets. The third investigated problem concerns the calculation of the permanent. The permanent is a function on a matrix defined as the sum over the product of all valid permutations of the matrix. If the permanent is applied on the adjacency matrix of bipartite graph, it is equivalent to the number of perfect matchings of that graph.
Calculating the exact value of the permanent is #P-Complete and it is considered a fundamental problem in Theoretical Computer Science.
We focused on providing algorithms which could approximate the value of the permanent efficiently. For this purpose, investigated a previously known method and modified it through the use of matrix scaling. We then discussed an extension of the above method to be used as an estimator of the number of perfect matchings in general graphs. Extensive experimental analysis showed that the proposed methods could approximate the value of the permanent far more eectively than similar methods from the literature. The last investigated problem concerns the analysis of algorithms for the Birkhof-Von Neumann Decomposition of doubly stochastic matrices. This decomposition  expresses a doubly stochastic matrix as linear combination of permutations. It is NP-hard to find a decomposition with the least number of permutations used. We showed performance bounds for two heuristics.

Mots clés