Publication

How to Match in Modern Computational Settings

Résumé

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algorithm only knows the distribution from which the edges are sampled.In the query-commit model, the algorithm must query edges to know if they exist and is committed to adding all queried edges that exist to its output.In the price-of-information model, the algorithm incurs costs for querying edges, and the total query cost is subtracted from the output matching's weight.For maximum weighted matching in these models, previously known best algorithms were greedy algorithms that achieve 1/2 approximations. We improve the approximation ratio to 1 - 1/e in both models. Next, we consider situations where the input graphs do not fit into the space available for an algorithm instance. We consider two such models: the semi-streaming model where the algorithm receives the input as a stream of edges and the algorithm has only sub-linear (in the number of edges) space, and the massively parallel computation (MPC) model where the input is distributed among several machines, each of which has sub-linear space, and algorithm instances running on different machines must communicate in synchronous rounds.We start with a particular case of the semi-streaming model where the edges arrive in uniformly random order, and the algorithm goes over the stream only once. For this setting, we give the first algorithm that finds a (1/2 + c)-approximate maximum weighted matching in expectation; such algorithms were previously known only for the unweighted graphs.We then show how to efficiently find (1 - epsilon)-approximate weighted matchings for any epsilon > 0 in multi-pass semi-streaming and MPC models by extending our algorithmic ideas used in the single-pass semi-streaming model with random order edge arrivals.Finally, we study online algorithms for matching, where the input graph is gradually revealed over time. In the online edge-arrival setting, the graph is revealed one edge at a time, and an algorithm is forced to make irrevocable decisions on whether to add each edge to the output matching upon their arrival. We show that no online algorithm can achieve a competitive ratio of 1/2 + c for any constant c > 0 in this setting.In the online vertex-arrival setting, the graph is revealed one vertex at a time, together with its incident edges to already revealed vertices, and the algorithm must irrevocably decide to ignore the revealed vertex or match it to one of the available neighbors.In this setting, we show how to round a previously known fractional online matching algorithm to get an integral online matching algorithm with a competitive ratio of 1/2 + c for some constant c > 0.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (37)
Couplage (théorie des graphes)
En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.
Maximum weight matching
In computer science and graph theory, the maximum weight matching problem is the problem of finding, in a weighted graph, a matching in which the sum of weights is maximized. A special case of it is the assignment problem, in which the input is restricted to be a bipartite graph, and the matching constrained to be have cardinality that of the smaller of the two partitions. Another special case is the problem of finding a maximum cardinality matching on an unweighted graph: this corresponds to the case where all edge weights are the same.
Coloration des arêtes d'un graphe
thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.
Afficher plus
Publications associées (42)

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...
EPFL2023

SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators

Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus

We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...
JMLR-JOURNAL MACHINE LEARNING RESEARCH2022

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.