Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Efficient Algorithm for Fully Robust Stable Matchings via Join Semi-Sublattices
109
0
0.0
(
0
)
Added by
Tung Mai
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We are given a stable matching instance $A$ and a set $S$ of errors that can be introduced into $A$. Each error consists of applying a specific permutation to the preference list of a chosen boy or a chosen girl. Assume that $A$ is being transmitted over a channel which introduces one error from set $S$; as a result, the channel outputs this new instance. We wish to find a matching that is stable for $A$ and for each of the $|S|$ possible new instances. If $S$ is picked from a special class of errors, we give an $O(|S| p(n))$ time algorithm for this problem. We call the obtained matching a fully robust stable matching w.r.t. $S$. In particular, if $S$ is polynomial sized, then our algorithm runs in polynomial time. Our algorithm is based on new, non-trivial structural properties of the lattice of stable matchings; these properties pertain to certain join semi-sublattices of the lattice. Birkhoffs Representation Theorem for finite distributive lattices plays a special role in our algorithms.
rate research
Read More
Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. It has been suggested that finding an MIS is equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching of a network is often not unique, and finding all MISs may provide deep insights to the controllability of the network. Finding all possible input nodes, which form the union of all MISs, is computationally challenging for large networks. Here we present an efficient enumerative algorithm for the problem. The main idea is to modify a maximum matching algorithm to make it efficient for finding all possible input nodes by computing only one MIS. We rigorously proved the correctness of the new algorithm and evaluated its performance on synthetic and large real networks. The experimental results showed that the new algorithm ran several orders of magnitude faster than the existing method on large real networks.
We consider networks of small, autonomous devices that communicate with each other wirelessly. Minimizing energy usage is an important consideration in designing algorithms for such networks, as battery life is a crucial and limited resource. Working in a model where both sending and listening for messages deplete energy, we consider the problem of finding a maximal matching of the nodes in a radio network of arbitrary and unknown topology. We present a distributed randomized algorithm that produces, with high probability, a maximal matching. The maximum energy cost per node is $O(log^2 n)$, where $n$ is the size of the network. The total latency of our algorithm is $O(n log n)$ time steps. We observe that there exist families of network topologies for which both of these bounds are simultaneously optimal up to polylog factors, so any significant improvement will require additional assumptions about the network topology. We also consider the related problem of assigning, for each node in the network, a neighbor to back up its data in case of node failure. Here, a key goal is to minimize the maximum load, defined as the number of nodes assigned to a single node. We present a decentralized low-energy algorithm that finds a neighbor assignment whose maximum load is at most a polylog($n$) factor bigger that the optimum.
We provide necessary and sufficient conditions on the preferences of market participants for a unique stable matching in models of two-sided matching with non-transferable utility. We use the process of iterated deletion of unattractive alternatives (IDUA), a formalisation of the reduction procedure in Balinski and Ratier (1997), and we show that an instance of the matching problem possesses a unique stable matching if and only if IDUA collapses each participant preference list to a singleton. (This is in a sense the matching problem analog of a strategic game being dominance solvable.)
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).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
