# Tag Info

## Hot answers tagged matching

13 votes
Accepted

### A problem with the greedy approach to finding a maximal matching

You're correct, you're not missing anything -- except that the algorithm is not wrong. The task is to choose a maximal matching, not a maximum matching. There may be many possible maximal matchings, ...
• 141k
10 votes
Accepted

• 13.2k
4 votes

### Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is ...
• 1,682
4 votes

### state of the art of subset, set containment and partial match queries

I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.
• 1,287
4 votes
Accepted

### Changing preference in Gale-Shapley algorithm?

The property your wish to prove is known as strategy proofness: Is it possible for an agent to report a preference $P'$ such that it gets matched to a strictly better result w.r.t. its true preference ...
• 6,978
4 votes
Accepted

### Determine whether two collections of items can be paired

Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with. ...
• 80.3k
4 votes

### What is a fractional matching?

The formal definitions are very nice, but here's a simplier more intuitive explanation. In a fractional matching, every edge has a number. The sum all all the edge numbers connected to any vertex must ...
• 291
4 votes
Accepted

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.
• 270k
4 votes
Accepted

### one-to-many matching in bipartite graphs?

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a ...
• 4,083
4 votes
Accepted

### Weighted Online Matching - randomized algorithms

A randomized algorithm cannot be constant-competitive in worst-case order. A proof using Yao's principle can be found here.
• 56
4 votes
Accepted

### Find a perfect matching with weights as close as possible to each other

You haven't specified what you mean by "as close as possible to each other", so let me assume that you want to minimize the difference between the minimal weight and the maximal weight. ...
• 270k
3 votes
Accepted

### Equality of cardinality of maximum matching and minimum vertex cover in general

Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if ...
• 270k

Only top scored, non community-wiki answers of a minimum length are eligible