The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged matching

9

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 otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$. An ...

8

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs. Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform ...

8

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 neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is ...

7

Yes, the stable marriage problem still makes sense with unequal arrays. Permit me to use men and women as opposed to students and dorms. There are different stable matchings that you can ask for resulting in different cases. A specific stable matching is desired, either male optimal or female optimal solution Any valid stable matching is desired All the ...

7

Counting the number of perfect matchings in bipartite graphs amounts to computing the permanent of 0–1 matrices, which is $\# P$-complete. It follows that there is a reduction from all the other counting problems you mention (which are all in $\# P$) to this problem. You can compute the number of perfect matchings in planar bipartite graphs, and you ...

7

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 problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph. Suppose we have a bipartite graph ...

7

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 $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), ...

7

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 graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the ...

7

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 even on graphs with maximum degree 3.

6

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 be connected to two vertices. So instances where someone doesn't want to speak to 3 or more other people cannot be modeled.

6

A matching in which all the vertices in $A$ are matched is known as a perfect matching. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is ...

6

There's an enormous amount of work on data structures and algorithms for this sort of problem. I suggest you start by reading the general literature on this problem. Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem. Those techniques are applicable to your problem. ...

6

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 literature and can be solved in polynomial time with a reduction to the Assignment Problem. With the introduction of colors to the problem, it is NP-hard (and ...

6

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 constraints that $\sum_{w\in N(v)} f(v,w) \leq1$ for all $v \in V$ are the constraints that define the matching problem where for each $e \in E$, $f(e)$ is a ...

5

You can add $5$ dummy students, and put them low in the dorms' preference order. The resulting perfect matching $\pi$ will have the following two properties: There is no student $s$ and dorm $d$ which are not matched such that $s$ prefers $d$ to $\pi(s)$ and $d$ prefers $s$ to $\pi(d)$. There is no student $s$ and empty dorm $d$ such that $s$ prefers $d$ to ...

5

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 literature where this is described. It is also described here: The stable marriage algorithm with asymmetric arrays. See also https://cs.stackexchange.com/a/...

5

I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata. The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM, 11(6):419-422, June 1968. But that ...

5

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 could end up with a sub-optimal solution of On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates ...

4

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 model, given a graph you would like to write one linear program, changing whose objective function gives you the right matching corresponding to any weight ...

4

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$ if $W'$ is empty. We similarly define $\max_w M'$ for a woman $w$ and a set $M'$ of men. One way to view the Gale–Shapley algorithm is as maintaining a graph $G$...

4

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 $P$ than reporting truthfully? Note that while the GS algorithm is strategy proof for the men, it is not for the women: they can use misrepresenting the ...

4

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 close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, ...

4

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. There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.

4

"Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching". Your graph is NOT a tree as it has a cycle $0, 1, 2, 0$. Furthermore, your graph does have a perfect matching. In fact, the edges $(2,3)$ and $(0,1)$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our ...

4

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 for maximum weight matching in general graphs.

4

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 be less than 1.

3

In general, you won't be able to marry all but one of the men and all but one of the women. For example, suppose that all of the men want to marry the same four women: you'll get exactly four marriages and an arbitrarily large number of bachelors and spinsters.

3

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, and then we can read from the graph a stable matching, indeed both the man-optimal and the woman-optimal stable matchings. For this view, check out for ...

3

This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.

3

Well these patterns will make KMP work faster: T=aaaaaaaaaa P=aaaa KMP will try 10 compare steps were Boyer-Moore will take 28 Another example: T=aaaaaaaaaa P=abab KMP will try 8 compare steps where BM will try 12.

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