All Questions
Tagged with matching-theory discrete-optimization
20
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
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
102
views
Multiset Matching
Suppose we have two multisets of positive integers, $A$ and $B$, where the sum of the elements (counted with multiplicity) of the two multisets is the same. Starting from $A$, we would like to arrive ...
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
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
1
vote
1
answer
434
views
Why is the size of a minimum vertex cover always greater than or equal to a maximal matching?
The topic I am dealing with right now is a 2-approximation algorithm for the minimum vertex cover. The proof seems fairly simple but I don't understand one assumption that is made.
It is the ...
- 453
0
votes
1
answer
311
views
Assignment problem with multiple assignments and constraints
I have a bi-partite graph $G=(P \cup C,E)$ where $P$ contains 'parents', these parents are in pairs, but count as one vertex, and are to be matched with a number of children in the set $C$. I want to ...
- 31
0
votes
2
answers
528
views
Does a bipartite graph without perfect matching exist?
I know that not all bipartite graphs have perfect matching, but I am having trouble coming up with an example (I'm a visual learner). Can someone give me a visual example of a bi[artite graph without ...
- 1,583
7
votes
1
answer
132
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
3
votes
1
answer
184
views
Hungarian Algorithm: Sequence of Choices
I'm thinking about utilizing the Hungarian algorithm for a research problem. I need to better understand what's happening behinds the scenes. I'm utilizing the matrix version.
The algorithm proceeds ...
- 280
0
votes
0
answers
48
views
Optimal spacing between curves
This question will make brief forays beyond pure mathematics and into the world of application, so bear with me. This question also requires some small setup.
First, I have a set of functions,
$$\...
- 143
0
votes
2
answers
200
views
How to write the optimization constraint of the following problem
$A$ is an adjacency matrix and $W$ is the weight matrix.
So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
- 221