Problème des mariages stables

Résumé

vignette|Algorithme de Gale Shapley. En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il y a au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels (Dupont préfère à , et préfère Dupont à Durand). Ce problème a des applications en économie, en théorie des jeux et en physique statistique. On sait trouver une solution stable, mais il en existe en général un grand nombre et l'on ne sait pas les trouver toutes, quand n est grand. On peut modifier l'énoncé en lui ajoutant une condition d'optimisation : il existe alors une solution optimale (ou plusieurs mais équivalentes), mais on ne sait pas la ou les trouver avec certitude, juste appliquer différents algorithmes, plus ou moins performants.

Source officielle

https://fr.wikipedia.org/wiki/Probl%C3%A8me_des_mariages_stables

À 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.

Publications associées (21)

Publications associées

Chargement

Personnes associées (4)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (2)

Concepts associés

Chargement

Cours associés (3)

Cours associés

Chargement

Séances de cours associées (7)

Afficher plus

Séances de cours associées

Chargement

Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

Yuri Faenza, Gautier Stauffer

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.

2012

Chargement

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also been numerous works that study combinatorial problems with submodular objective functions. This is motivated by their natural diminishing returns property which is useful in real-world applications. The thesis at hand is concerned with the study of streaming and matching problems with submodular functions.Firstly, motivated by developing robust algorithms, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We study the maximum matching problem and cardinality constrained monotone submodular maximization. We show that even under this seemingly powerful adversary, it is possible to break the barrier of 1/2 for both these problems in the streaming setting. Our main result is a novel streaming algorithm that computes a 0.55-approximation for cardinality constrained monotone submodular maximization.In the second part of the thesis, we study the problem of matroid intersection in the semi-streaming setting. Our main result is a (2 + e)-approximate semi-streaming algorithm for weighted matroid inter- section improving upon the previous best guarantee of 4 + e. While our algorithm is based on the local ratio technique, its analysis differs from the related problem of weighted maximum matching and uses the concept of matroid kernels. We are also able to generalize our results to work for submodular functions by adapting ideas from a recent result by Levin and Wajc (SODA'21) on submodular maximization subject to matching constraints.Finally, we study the submodular Santa Claus problem in the restricted assignment case. The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function fi. The goal is to maximize mini fi(Si) where S1, . . . , Sm is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n1/2+e)-approximation algorithm. In the restricted assignment case, each player is given a set of desired resources Gi and the individual valuation functions are defined as fi(S)= f(SnGi). OurmainresultisaO(loglog(n))-approximation algorithm for the problem. Our proof is inspired by the approach of Bansal and Srividenko (STOC'06) to the Santa Claus problem. Com- pared to the more basic linear setting, the introduction of submodularity requires a much more involved analysis and several new ideas.

EPFL2022

Chargement

In this thesis, we explore possible stabilisation methods for the reduce basis approximation of advection-diffusion problems, for which the advection term is dominating. The options we consider are mainly inspired by the Variational Multiscale method (VMS), which decomposes the solution of a variational problem into its coarse scale component, from a coarse scale space, and a fine scale component, from a fine scale space. Our stabilisation proposals are divided into three classes. The first one groups methods that rely on a stabilisation parameter. The second class uses VMS at the algebraic level to attempt stabilisation. Finally the third class is also inspired by VMS at the algebraic level, but with the additional constraint that the fine scale space is orthogonal to the coarse scale space. Numericals tests reported in this thesis show that the methods of the first class is not viable options as the best stabilisation parameter among those tested is the stabilisation parameter that is used at the high fidelity level. Although the stabilisation methods of the second class give accurate results when applied to stable problems, they were also dismissed by the numerical tests, as they did not improve the accuracy of the already stabilised problem. The third class also performs well when applied to stable problems. It has been shown in [7] one of those methods can improve accuracy. However in the current implementation, this result was not achieved here.

2016

Chargement

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

EPFL2022