Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaintaining Perfect Matchings at Low Cost
62
0
0.0
(
0
)
Added by
Ulrike Schmidt-Kraepelin
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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. On the other hand, one expects that small changes in the input should incur only small changes on the constructed solutions, measured as the number of modified edges. We introduce a two-stage model where we study the trade-off between quality and robustness of solutions. In the first stage we are given a set of nodes in a metric space and we must compute a perfect matching. In the second stage $2k$ new nodes appear and we must adapt the solution to a perfect matching for the new instance. We say that an algorithm is $(alpha,beta)$-robust if the solutions constructed in both stages are $alpha$-approximate with respect to min-cost perfect matchings, and if the number of edges deleted from the first stage matching is at most $beta k$. Hence, $alpha$ measures the quality of the algorithm and $beta$ its robustness. In this setting we aim to balance both measures by deriving algorithms for constant $alpha$ and $beta$. We show that there exists an algorithm that is $(3,1)$-robust for any metric if one knows the number $2k$ of arriving nodes in advance. For the case that $k$ is unknown the situation is significantly more involved. We study this setting under the metric on the line and devise a $(10,2)$-robust algorithm that constructs a solution with a recursive structure that carefully balances cost and redundancy.
rate research
Read More
We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in a arbitrary graph. Finally, we give exact counting algorithms for three classes.
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G subseteq K_{n,n}$ has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $G subseteq K_{n,n}$ contains one of these minimum weight perfect matchings.
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 that an applicant $x in A$ prefers an item p than an item q if p is located at a higher position than q in its preference list, and we say that x prefers a matching M over a matching M if x prefers M(x) over M(x). For a given matching problem A, I, and preference lists, we say that M is more popular than M if the number of applicants preferring M over M is larger than that of applicants preferring M over M, and M is called a popular matching if there is no other matching that is more popular than M. Here we consider the situation that A is partitioned into $A_{1},A_{2},...,A_{k}$, and that each $A_{i}$ is assigned a weight $w_{i}>0$ such that w_{1}>w_{2}>...>w_{k}>0$. For such a matching problem, we say that M is more popular than M if the total weight of applicants preferring M over M is larger than that of applicants preferring M over M, and we call M an k-weighted popular matching if there is no other matching that is more popular than M. In this paper, we analyze the 2-weighted matching problem, and we show that (lower bound) if $m/n^{4/3}=o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} geq 2w_{2}$ has a 2-weighted popular matching with probability o(1); and (upper bound) if $n^{4/3}/m = o(1)$, then a random instance of the 2-weighted matching problem with $w_{1} geq 2w_{2}$ has a 2-weighted popular matching with probability 1-o(1).
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).
A family of perfect matchings of $K_{2n}$ is $t$-$intersecting$ if any two members share $t$ or more edges. We prove for any $t in mathbb{N}$ that every $t$-intersecting family of perfect matchings has size no greater than $(2(n-t) - 1)!!$ for sufficiently large $n$, and that equality holds if and only if the family is composed of all perfect matchings that contain a fixed set of $t$ disjoint edges. This is an asymptotic version of a conjecture of Godsil and Meagher that can be seen as the non-bipartite analogue of the Deza-Frankl conjecture proven by Ellis, Friedgut, and Pilpel.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
