A matching (aka **Independent Edge Set**) in a simple graph is the set of pairwise non-adjacent edges i.e. no two edges have common vertex.
0
votes
0answers
13 views
Algorithm for finding the minimum-weight perfect matching
I was going through the [Christofides algorithm](minimum-weight perfect matching) but got stuck stuck when I had to find the minimum-weight perfect matching.
What is the easiest way to find the ...
0
votes
1answer
28 views
Stable matching with asymmetric arrays (gale shapley)
I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms.
One of the answer ...
0
votes
0answers
27 views
min-weight perfect matching for christofides algorithm
I read all the topics like:
Min-weight bipartite matching in Christofides' algorithm
Faster maximum weight matching algorithm in bipartite graph
but I still don't understand one step in coding ...
3
votes
1answer
51 views
Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?
I came across this problem in Tim Roughgarden's course on Coursera:
In this problem you are given as input a graph $T=(V,E)$ that is a
tree (that is, $T$ is undirected, connected, and acyclic). A ...
2
votes
0answers
40 views
Edmond's Blossom algorithm (Maximum Matching) explanation
I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here.
Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
3
votes
1answer
33 views
Maximizing quantities/length in buckets to match each other
I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it.
I'll try to simplify, with a simple analogue, and after will explain the real world use ...
3
votes
1answer
24 views
Determine whether two collections of items can be paired
Given collections I (items) and S (slots), where I >= S.
And a pairing function that ...
1
vote
1answer
26 views
Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?
I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching.
However, I am using python-graph-tool, which only has max-cardinality ...
1
vote
1answer
214 views
Algorithm for matching people
I work at a summer camp where one of the activities is called Speed Dating. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people ...
2
votes
1answer
63 views
Which algorithm can calculate an optimal allocation of students to projects?
I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
0
votes
0answers
20 views
Hopcroft und Karp Algorithm and a suitable representation for a graph
Hey Guys I have a small question about the Hopcroft and Karp Algorithm.
I have a task to solve where I have to calculate the perfect matching. My professor told me I should use the Hopcroft Algorithm....
3
votes
1answer
67 views
Is a perfect matching's weight less than MST of a metric graph?
This is part of a bigger proof I'm trying to solve, which eventually came down to one thing:
Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even ...
3
votes
1answer
74 views
Students in classroom problem - Flow in network
I have room, which is opened some days in week, in different hours each day.
I have multiple students, each has time some days in week, in different hours.
Each student have to visit the room ...
2
votes
2answers
33 views
Can a perfect matching always be found by a picking sequence?
There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference ...
0
votes
0answers
20 views
Is implementation of approximate dynamic maximal matching feasible?
I'm wondering if algorithms described in:
https://ieeexplore.ieee.org/abstract/document/7782946/
http://drops.dagstuhl.de/opus/volltexte/2014/4845/
easy to implement. They seem to mention the word "...
0
votes
0answers
27 views
Determine an $O(nlog n)$ time algorithm for maximum matching in a bipartite graph for dominating points
You are given a set A of n points in the plane, and a set B of n points in the plane. There is a bipartite graph with edges from A to B if and only if the point in B dominates the point in A for all ...
1
vote
1answer
34 views
Group tuples to satisfy constraints
This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced ...
0
votes
0answers
15 views
Enumerate all (n-1) edge disjoint perfect matchings in complete (undirected) graphs
What would be the most efficient way to do this?
It'd be helpful if I could get inputs on optimizing the brute force method as well (generate all the perfect matchings; then check all n-1 perfect ...
1
vote
0answers
52 views
Best algorithm to generate matchmaking pairs
I am trying to come up with a matchmaking algorithm based on player ratings for my game, and I am pretty sure the algorithm I have is not the best (or maybe doesn't even work), but have no idea how to ...
1
vote
1answer
272 views
Which algorithm for game matchmaking in tournament
I organize amateur tournaments every week with random players.
Every week, players sign up, and I get a list with:
Name
Rank (1, 2 or 3)
Role (s) (DPS, TANK and HEALER)
I need to get balanced teams ...
1
vote
1answer
422 views
Perfect matching in a bipartite regular graph in linear time
Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time.
It is easy to show that there is a perfect matching for the graph, by using flow and ...
0
votes
0answers
67 views
Polynomial time algorithm to decide whether it is possible to keep set of phones fully connected (Kleinberg 7.26)
This is a problem from Kleinberg & Tardos textbook.
We are given the locations of n base stations, specified as points b1, . . . , bn in the plane. We are also given the locations of n cellular ...
0
votes
0answers
11 views
Confusion over irvings algorithm
It is my understanding that the algorithm can be broken down into 3 steps.
1) Make a proposal
2) Role out worst matches
3) Eliminate Rotations (Cyclical pattern)
I have been able to test out the ...
3
votes
1answer
270 views
Changing preference in Gale-Shapley algorithm?
Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm.
If a man were to switch the order of a pair of women, ...
0
votes
2answers
36 views
maximum matching number decreases when vertices collapse?
It seems that the maximum matching number decreases when some independent (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true.
Would maximum matching number ...
6
votes
0answers
84 views
Complexity of removing edges to eliminate a perfect matching
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
0
votes
1answer
29 views
Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup
I've been trying to solve the following question:
Show a polynomial algorithm for the following problem. Let $G = (V,
> E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that
for ...
1
vote
2answers
243 views
Stable matching problem is greedy or Dynamic?
Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
0
votes
1answer
460 views
How to use stable matching algorithm in order to determine optimal schedule?
This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos:
There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month ...
1
vote
1answer
57 views
Understanding characterizations of Matching on Graphs
I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.
Definition:
Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching ...
1
vote
0answers
103 views
Optimal Preference Matching
I'm trying to find an algorithm that finds an optimal matching between $A$ and $B$, where each element $a$ of $A$ provides a preference order $\prec_a$ over $B$. I will notate the index of an element $...
1
vote
1answer
152 views
Matching with One-sided Preferences
I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where:
Set $A$ has an incomplete set of preferences (not all of $B$ is included)
Set $B$ has no preferences ...
1
vote
0answers
48 views
finding the minimal subset in bipartite graph violating halls condition
I want to find the minimal subset in bipartite graph violating Hall's condition.
More specifically, given a bipartite graph $(S_1,S_2，E)$, finding the minimum cardinality subset of right-vertices $S_2$...
1
vote
1answer
94 views
Weighted Matching with multiple assignments and min assignments
I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, ...
0
votes
1answer
69 views
information about matching algorithms?
I have been searching for matching algorithms similar to the Gale Shapley, or stable marriage algorithm, but with no luck.
The question is if there are other algorithms that are similar to the GS and ...
3
votes
1answer
134 views
state of the art of subset, set containment and partial match queries
The subset query problem is defined as:
Given a list D of size N where the entries are subsets of a universe with ...
3
votes
1answer
50 views
Matching points between 2 polygons
Given 2 polygons in a plane:
$A : ( (xa_1,ya_1), (xa_2,ya_2), ... (xa_n,ya_n) )$
$B : ( (xb_1,yb_1), (xb_2,yb_2), ... (xb_m,yb_m) )$
Is there a polynomial algorithm to compute a matching $M$ ...
1
vote
1answer
51 views
Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$?
Berge's theorem: a matching $M$ is maximum if and only if the graph doesn't have an augmenting path with respect to $M$.
I don't understand this theorem. For instance the following matching is ...
1
vote
0answers
138 views
Matching odd-degree nodes in an undirected graph
The Chinese Postman problem (A.K.A Route Inspection Problem)
I'm trying to match pairs of odd-degree nodes in a grid-graph representing an indoor map to ensure the graph is Eulerian (consists only of ...
2
votes
2answers
217 views
Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?
I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution
Senario: We have a boy and girl, the boy has completed his profile/bio ...
3
votes
1answer
645 views
Does Gale-Shapley work when the number of men and women are not equal?
According to the Wikipedia page on the Stable Marriage Problem, the problem is presented in a way in which the number of men and women are both the same.
Given n men and n women, where each person ...
-1
votes
1answer
112 views
Definition of valid partner in Stable Matching Problem
From Tardos and Kleinberg's Algorithm Design, the definition for "worse valid partner" is basically — $m$ is $w$'s worse valid partner if $m$ is a valid partner of $w$, and no man whom $w$ ranks ...
1
vote
0answers
23 views
Maximal Matching of nodes that fall into four categories
Nodes have values. Node n's value is denoted n.val. Two or more nodes can have the same value.
A node ...
1
vote
0answers
144 views
approximation algorithm of k-set packing
For my application problem, I am looking for an easy to implement or source code for approximation algorithm for maximum k-Set Packing problem.
Given a universe $U$ and a family $ \mathcal{S} $ of ...
3
votes
0answers
33 views
Looking for a matching-like mapping with a spread constraint
I am doing a project on task assignment with geographic constraints which naturally leads to the following question.
Let $\mathbb{N}$ denote the set of integers. Given a finite subset $A \subset \...
3
votes
0answers
216 views
Optimal pairing of points in a set
I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the ...
3
votes
0answers
36 views
Properties of the filtered preference list (phase 1) in the Stable Roommates problem
I'm currently working my way through An Efficient Algorithm for the “Stable Roommates” Problem by Robert Irving (Journal of Algorithms, 6:577–595, 1984).
On page 7 the paper starts with ...
4
votes
1answer
381 views
Show that the following algorithm doesn't always find the optimal matching
Consider the following algorithm for the maximum matching problem:
Sort all nodes by their $\deg(v)$
Take the node with minimal $\deg(v)$
Take a random edge $(u,v)$ $\in$ $E$
Add $(u,v)$ to $M$
...
0
votes
0answers
140 views
Edge incident to cut-vertex not in perfect matching of a graph
Let G = (V,E) be a connected graph and a ∈ V be an articulation point of G. How can be proved that there is an edge e ∈ G incident with a with the property that e doesn't belong to a perfect matching ...
0
votes
0answers
590 views
Minimum cost perfect matching (Using General graph
This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution.
I'...
