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, ...
user avatar
  • 141k
10 votes
Accepted

Why is Savage's Vertex Cover algorithm a 2-approximation?

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node. Next, we show that the DFS tree has a matching of size at least $|...
user avatar
10 votes

Complexity of Hopcroft-Karp

The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since ...
user avatar
8 votes
Accepted

What is a fractional matching?

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the ...
user avatar
  • 6,978
7 votes

Find perfect matching whose weight is minimal, in polynomial time

Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your ...
user avatar
  • 141k
7 votes
Accepted

Perfect matching in a graph and complete matching in bipartite graph

These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite ...
user avatar
7 votes
Accepted

Show that the following algorithm doesn't always find the optimal matching

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal ...
user avatar
7 votes

Game on the graph with matchings

First of all, let me correct maximal matchings (that is, matchings which cannot be extended) to maximum matchings (that is, matchings of maximal size). Suppose first that the starting vertex $v$ doesn'...
user avatar
6 votes
Accepted

Set of vertex-disjoint cycles maximizing different colored vertices

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP. Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange ...
user avatar
  • 497
6 votes
Accepted

Why can't we solve the dinner party problem by finding a maximum matching?

The problem is that you can not model all instances of the problem in the way you suggest: A person can be 'not on speaking terms' with arbitrarily many other persons, but an edge in a graph can only ...
user avatar
  • 6,519
6 votes

What is a fractional matching?

To add to Discrete lizard's answer, I would recommend you look into mathematical programming and optimization. The matching problem can be modelled as what is called an integer program (in fact the ...
user avatar
5 votes

Finding a perfect matching using an LP

The lower bounds on extended formulations (the one by Rothvoss for example) are lower bounds for a very specific way of using Linear Programming to solve a problem (matching in this case). In this ...
user avatar
  • 61
5 votes
Accepted

Stable marriage problem with only one side having preferences

The answer to your first question is: yes, there is a simple augmentation. It is described in the standard literature on the stable marriage problem. See the Wikipedia article for references in the ...
user avatar
  • 141k
5 votes
Accepted

Perfect matching in a bipartite regular graph in linear time

There is a classical linear time algorithm of Gabow and Kariv. The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you ...
user avatar
5 votes
Accepted

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you ...
user avatar
  • 34.1k
5 votes
Accepted

Can maximum matching algorithms be used for maximum weight matching?

Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms ...
user avatar
5 votes

How to match two point sets to minimize total distance?

This is an instance of the assignment problem and can be solved with standard algorithms for that problem.
user avatar
  • 141k
4 votes

Gale–Shapley algorithm is man-optimal

We use the following notation: $M$ is the set of men, $W$ the set of women. For a man $m$ and a set $W'$ of women, $\max_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ ...
user avatar
4 votes
Accepted

Could an alternating approach yield a fairer solution to the stable marriage problem?

The idea of the Gale-Shapley algorithm is to consider the graph of possible matchings (i.e. marriages) and trim edges that cannot happen in a stable matching. Eventually, we cannot trim any more edges,...
user avatar
4 votes
Accepted

Correctness proof: 2-approximation of greedy matching-algorithm

Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching). For all $e\in M'$ let $M_e\...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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.
user avatar
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 ...
user avatar
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.
user avatar
  • 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. ...
user avatar
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 ...
user avatar

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