Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWeighted Random Popular Matchings
128
0
0.0
(
0
)
Added by
Toshiya Itoh
Publication date
2007
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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).
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 of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $ell ge 1$ the problem of finding a minimum weight maximal distance-$2ell$ matching and the problem of finding a minimum weight $(2 ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $delta ln |V(G)|$ unless $mathrm{P} = mathrm{NP}$, where $delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs.
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, for example in the form of NP-hardness and the (Strong) Exponential Time Hypothesis. In practice however, SAT instances can often be solved efficiently. This contradicting behavior has spawned interest in the average-case analysis of SAT and has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, most theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a non-uniform distribution of the variables, which can result in distributions closer to industrial SAT instances. We study satisfiability thresholds of non-uniform random $2$-SAT with $n$ variables and $m$ clauses and with an arbitrary probability distribution $(p_i)_{iin[n]}$ with $p_1 ge p_2 ge ldots ge p_n > 0$ over the n variables. We show for $p_1^2=Theta(sum_{i=1}^n p_i^2)$ that the asymptotic satisfiability threshold is at $m=Theta( (1-sum_{i=1}^n p_i^2)/(p_1cdot(sum_{i=2}^n p_i^2)^{1/2}) )$ and that it is coarse. For $p_1^2=o(sum_{i=1}^n p_i^2)$ we show that there is a sharp satisfiability threshold at $m=(sum_{i=1}^n p_i^2)^{-1}$. This result generalizes the seminal works by Chvatal and Reed [FOCS 1992] and by Goerdt [JCSS 1996].
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.
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 in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
