ﻻ يوجد ملخص باللغة العربية
For a set $A$ of $n$ people and a set $B$ of $m$ items, with each person having a preference list that ranks all items from most wanted to least wanted, we consider the problem of matching every person with a unique item. A matching $M$ is called $epsilon$-popular if for any other matching $M$, the number of people who prefer $M$ to $M$ is at most $epsilon n$ plus the number of those who prefer $M$ to $M$. In 2006, Mahdian showed that when randomly generating peoples preference lists, if $m/n > 1.42$, then a 0-popular matching exists with $1-o(1)$ probability; and if $m/n < 1.42$, then a 0-popular matching exists with $o(1)$ probability. The ratio 1.42 can be viewed as a transition point, at which the probability rises from asymptotically zero to asymptotically one, for the case $epsilon=0$. In this paper, we introduce an upper bound and a lower bound of the transition point in more general cases. In particular, we show that when randomly generating each persons preference list, if $alpha(1-e^{-1/alpha}) > 1-epsilon$, then an $epsilon$-popular matching exists with $1-o(1)$ probability (upper bound); and if $alpha(1-e^{-(1+e^{1/alpha})/alpha}) < 1-2epsilon$, then an $epsilon$-popular matching exists with $o(1)$ probability (lower bound).
For a set A of n applicants and a set I of m items, we consider a problem of computing a matching of applicants to items, i.e., a function M mapping A to I; here we assume that each applicant $x in A$ provides a preference list on items in I. We say
We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose--accept rounds executed by the Gale--Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost s
The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, adding two nodes to the input might change the optimal solution completely
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching i
We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue o