Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
50
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 study a natural generalization of stable matching to the maximum weight stable matching problem and we obtain a combinatorial polynomial time algorithm for it by reducing it to the problem of finding a maximum weight ideal cut in a DAG. We give the first polynomial time algorithm for the latter problem; this algorithm is also combinatorial. The combinatorial nature of our algorithms not only means that they are efficient but also that they enable us to obtain additional structural and algorithmic results: - We show that the set, $cal M$, of maximum weight stable matchings forms a sublattice $cal L$ of the lattice $cal L$ of all stable matchings. - We give an efficient algorithm for finding boy-optimal and girl-optimal matchings in $cal M$. - We generalize the notion of rotation, a central structural notion in the context of the stable matching problem, to meta-rotation. Just as rotations help traverse the lattice of all stable matchings, macro-rotations help traverse the sublattice over $cal M$.
rate research
Read More
We introduce a novel method for defining geographic districts in road networks using stable matching. In this approach, each geographic district is defined in terms of a center, which identifies a location of interest, such as a post office or polling place, and all other network vertices must be labeled with the center to which they are associated. We focus on defining geographic districts that are equitable, in that every district has the same number of vertices and the assignment is stable in terms of geographic distance. That is, there is no unassigned vertex-center pair such that both would prefer each other over their current assignments. We solve this problem using a version of the classic stable matching problem, called symmetric stable matching, in which the preferences of the elements in both sets obey a certain symmetry. In our case, we study a graph-based version of stable matching in which nodes are stably matched to a subset of nodes denoted as centers, prioritized by their shortest-path distances, so that each center is apportioned a certain number of nodes. We show that, for a planar graph or road network with $n$ nodes and $k$ centers, the problem can be solved in $O(nsqrt{n}log n)$ time, which improves upon the $O(nk)$ runtime of using the classic Gale-Shapley stable matching algorithm when $k$ is large. Finally, we provide experimental results on road networks for these algorithms and a heuristic algorithm that performs better than the Gale-Shapley algorithm for any range of values of $k$.
We study a discrete version of a geometric stable marriage problem originally proposed in a continuous setting by Hoffman, Holroyd, and Peres, in which points in the plane are stably matched to cluster centers, as prioritized by their distances, so that each cluster center is apportioned a set of points of equal area. We show that, for a discretization of the problem to an $ntimes n$ grid of pixels with $k$ centers, the problem can be solved in time $O(n^2 log^5 n)$, and we experiment with two slower but more practical algorithms and a hybrid method that switches from one of these algorithms to the other to gain greater efficiency than either algorithm alone. We also show how to combine geometric stable matchings with a $k$-means clustering algorithm, so as to provide a geometric political-districting algorithm that views distance in economic terms, and we experiment with weight
We survey our understanding of classical novae: non-terminal, thermonuclear eruptions on the surfaces of white dwarfs in binary systems. The recent and unexpected discovery of GeV gamma-rays from Galactic novae has highlighted the complexity of novae and their value as laboratories for studying shocks and particle acceleration. We review half a century of nova literature through this new lens, and conclude: --The basics of the thermonuclear runaway theory of novae are confirmed by observations. The white dwarf sustains surface nuclear burning for some time after runaway, and until recently, it was commonly believed that radiation from this nuclear burning solely determines the novas bolometric luminosity. --The processes by which novae eject material from the binary system remain poorly understood. Mass loss from novae is complex (sometimes fluctuating in rate, velocity, and morphology) and often prolonged in time over weeks, months, or years. --The complexity of the mass ejection leads to gamma-ray producing shocks internal to the nova ejecta. When gamma-rays are detected (around optical maximum), the shocks are deeply embedded and the surrounding gas is very dense. --Observations of correlated optical and gamma-ray light curves confirm that the shocks are radiative and contribute significantly to the bolometric luminosity of novae. Novae are therefore the closest and most common interaction-powered transients.
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a 0.382-approximate algorithm, significantly improving over the previous best 0.31-approximation of Baveja et al. (2018). When the vertices do not have patience constraints, we describe a 0.432-approximate random order probing algorithm with several corollaries such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show a 0.632-approximate algorithm that improves on the recent $1/3$-guarantee of Hikima et al. (2021).
We give an algorithm to find a mincut in an $n$-vertex, $m$-edge weighted directed graph using $tilde O(sqrt{n})$ calls to any maxflow subroutine. Using state of the art maxflow algorithms, this yields a directed mincut algorithm that runs in $tilde O(msqrt{n} + n^2)$ time. This improves on the 30 year old bound of $tilde O(mn)$ obtained by Hao and Orlin for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
