# Questions tagged [bipartite-matching]

The tag has no usage guidance.

143 questions
Filter by
Sorted by
Tagged with
18 views

### Creating an algorithm which utilizes an already known optimal solution to max matching

Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add ...
11 views

### Find a matching of a bipartite graph that uses all vertices in the left set

I have a bipartite graph already divided into a left and right set, and I would like to find a matching that uses all of the vertices in the left set. To phrase this problem less abstractly, I have a ...
21 views

### Algorithm for bipartite graph matching decision problem

Suppose I have a list of sets $$L=\{A_1,A_2,\ldots ,A_n\}$$ And want and algorithm that solves the following decision problem Is it possible to select one element from each set such that no two ...
63 views

### Hardness result for online matching

Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
43 views

### How to convert Bipartite Perfect Matching to SAT?

SAT is $NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin?
36 views

1k views

### Minimum cost to match $n$ people with $m$ shops

We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost ...
247 views

### Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...