# Questions tagged [matching]

For questions on matchings, i.e. sets of disjoint edges of an undirected graph.

16 questions
Filter by
Sorted by
Tagged with
133 views

### Effective methods for solving the assignment and packing problem

There are $m$ items to be allocated into $n$ bins. The profit generated by placing the $i$-th item into the $j$-th bin is $c_{ij}$, and the service level is $s_{ij}$. A allocation scheme is required ...
1 vote
131 views

### Exact algorithms for a bin packing problem

There is a one-dimensional bin-packing problem. There is a collection of items that need to be divided into several groups, with a maximum of M items per group. Each item includes several characters, ...
1 vote
115 views

### Matching algorithm in an order batching problem

There is an order batching problem. Given a set of orders, they need to be split into several batches, with a maximum order number of M per batch. Each order needs to be picked from multiple storage ...
1 vote
62 views

### What are the most popular papers on Uber-type spatial matching?

This is probably one of those "just google it" kinds of questions, but is there a commonly-accepted "definitive" model in the literature for capturing the kind of matching problem ...
103 views

71 views

### Maximal Matching in a constrained, unweighted Bipartite Graph

Suppose a set of partially connected nodes: All nodes are in set A xor in Set B (i.e. Bipartite Graph) All nodes have a datetime property. Connections in the ...
610 views

### Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In ...
73 views

### Finding an augmenting path or cycle in weighted graph

Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $n!$ perfect matchings in the ...