All Questions
Tagged with matching-theory linear-programming
8
questions
1
vote
0
answers
24
views
Is perfect matching anything special in the matching polytope?
Assume a $d$-regular graph $G$ has a perfect matching. I am wondering is the character function of the perfect matchings anything special in the matching polytope $P$ that is the convex hull of
$$\{\...
- 2,075
0
votes
1
answer
51
views
Proving that an edge is not an element of a matching.
Let $G$ be bipartite such that $G=(Y,E)$. Let $W \subset Y$ be a minimum vertex cover in $G$ and let $M \subset E$ be a maximum matching in bipartite graph $G$. Prove that for any edge $wy \in E$, if ...
- 9
1
vote
1
answer
298
views
How to write the dual problem (for stable matching)
How do you write the dual of the following problem - I know the basics behind the Lagrangian function but I'm getting a little confused with how to handle the Lagrangian multipliers when we are ...
- 329
0
votes
0
answers
43
views
Algorithm to solve 'user optimum' 'polygamic' stable marriage problem: Optimally assign travellers to shared rides.
I am looking for inspiration to reformulate the classical assignment problem into something behaviourally richer (closer to Nash equilibrium, or a stable marriage problem).
I find it tricky to ...
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
1
vote
0
answers
101
views
Solving Quadratic program for finding perfect matching in polynomial time
I am working on a variant of the assignment problem. The original assignment problem is as follows:
We are given a bipartite graph with 2n vertices. Each edge has a non-negative integer weight $w_{i,j}...
- 73
0
votes
2
answers
1k
views
finding bipartite matching (stable marriage problem)
Let $T=\{T_1 ...T_5 \}$ be a set of n=5 tutors and $L=\{L_1 ...L_7\}$ be the set of m=7 lectures.
The tutors specified lectures they would like to hold (preferences for $T$) and they specified which, ...
- 2,341
0
votes
0
answers
112
views
Derivation of the dual of the linear assignment problem
I read that the dual of the assignment problem is
$$
\begin{align} \text{maximize } & \sum_{i=1}^n \lambda_i + \sum_{i=1}^n \beta_i \\
& \lambda_i + \beta_j \leq c_{ij}
\end{align}
$$
where ...
- 1,572