All Questions
Tagged with matching-theory optimization
32
questions
-1
votes
3
answers
84
views
An Optimization Problem With Permutation Function [closed]
When I tried to solve an one-to-one assignment problem, I constructed it as the following optimization problem, which is a min-max optimization problem with the optimization objective being functions.
...
- 11
0
votes
0
answers
8
views
Bipartite Matching With Distant Constraints
I am investigating the complexity of the following problem.
Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
- 9
3
votes
1
answer
62
views
Greedy lemma Problem for matching spears to soldiers
The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is ...
- 307
2
votes
0
answers
51
views
Prove that $P_{\text {match }}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.
Problem: Prove that $P_{\text{match}}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.
My attempt:
Firstly, we prove that
$$\text{conv}\left\{\chi_M: M ...
- 1,238
2
votes
1
answer
100
views
Maximise $\sum_{x,y\in S} GCD(x,y)$ where $S = \{1,2,\ldots, 100\}$ and each number appears once in the sum
Question: One day Anindya and his friend Faria cooperated to play a fun game. They played to maximize the sum of points they gained throughout the game.
Let $S = \{1,2,\ldots, 100\}$. There are $50$ ...
user1270901
2
votes
1
answer
50
views
Understanding the proof perfect matching polytope
Theorem. Let $M$ and $N$ be perfect matchings in a graph $G=(V, E)$. Then $\chi^M$ and $\chi^N$ are adjacent vertices of the perfect
matching polytope if and only if $M \triangle N$ is a circuit.
...
- 873
1
vote
1
answer
62
views
Understanding the proof of Konig edge-colouring theorem
Theorem: (König's edge-colouring theorem). For any bipartite graph $G=(V, E)$,
$$
\chi(G)=\Delta(G) .
$$
That is, the edge-colouring number of a bipartite graph is equal to its maximum degree.
Proof. ...
- 873
2
votes
0
answers
116
views
Prove that symmetric difference of two perfect matchings is union of disjoint even cycles
Problem: Let $M$ and $N$ be perfect matchings of a finite graph $G$. Prove that their symmetric difference is a union of disjoint even cycles.
My attempt:
Firstly, if $M = N$, we are done.
Now, let us ...
- 1,238
0
votes
0
answers
55
views
Is there a way to do the Hungarian algorithm in reverse?
The Hungarian algorithm is used to find the optimal choices for a given 'cost matrix' e.g.
going from the output of the Hungarian algorithm
...
- 1
1
vote
0
answers
56
views
Hungarian Algorithm Adjustment Step
I am not sure whether I can simply not find an answer or I am just missing something obvious, but there is a step in the Hungarian algorithm which I am having trouble understanding; I will be ...
- 11
1
vote
1
answer
219
views
How to modify the hungarian algorithm for bipartite graphs with multiple edges with some already imposed connections
The Hungarian algorithm can be seen to take as input a complete weighted bipartite graph and outputs an optimal matching, maximising or minimising the sum of all the edges. Crucially, this algorithm ...
- 833
1
vote
0
answers
55
views
Finding a min weight matching of a specific size
For a complete graph $G=(V,E)$, i want to find a minimim weighted matching of a size $n$ where $n \leq \lvert V \rvert$ is there any known algorithms for such a problem other than IP formulations?
- 121
2
votes
1
answer
98
views
Points on a circle with maximum pairwise distance
We are given $n$ points on a circle of radius $1$ and an even number $k$. The distance $d(x,y)$ between two points $x$ and $y$ on the circle is given by the length of the (shorter) arc connecting them ...
- 89
1
vote
2
answers
180
views
Pairing cartesian coordinates for minimum distance
I have n start locations, defined by their x,y coordinates on a two-dimensional plane.
I have a further n destination locations (again, as x,y coordinates) that differ from the start locations.
All ...
- 13
1
vote
1
answer
20
views
How to assign a known number of different size of outbound packages, to a known (different) number of inbound deliveries?
I am trying to solve a problem that looks like the multiple knapsack problem, the multiple bin packing problem and the subset-sum problem, but isn't exactly one of them.
Imagine a warehouse where 4 ...
- 13