↑ arvau

Wikipedia / Maximum-weight matching

Maximum-weight matching is an optimization problem in graph theory in which the goal is to find a matching of maximum possible total weight in an edge-weighted graph. A matching is an independent edge set (that is, a set of edges in which none of the members share a common endpoint). The weight of a matching is the sum of the weights on its edges.

The problem is a generalization of the maximum cardinality matching problem because it allows edges to carry arbitrary numerical weights. When all edge weights are equal, a maximum-weight matching is equivalent to a maximum cardinality matching.

blossom algorithm algorithm. This contrasts with the problem of computing the (weighted) maximum independent set of vertices in a graph, which is NP-hard.

By adjusting the given edge weights, algorithms for the maximum-weight matching problem can also be used to solve the maximum cardinality maximum-weight matching problem, where the objective is to find, among all matchings with maximum cardinality, one whose total weight is maximised. Similar ideas can also be used to solve the maximum cardinality minimum weight matching problem. In cases where the edge-weighted graph is bipartite, such problems are also known as the assignment problem.

Definition

that maximises the total weight

The edge weights may be positive, negative, or mixed.

Maximum cardinality weighted matchings

A commonly occurring variant of the problem involves computing a matching that contains as many edges as possible. The total weight of the matching is then used as a secondary measure.

To solve the maximum-cardinality maximum-weight,

.

To solve the maximum cardinality minimum weight matching problem, set

.

. Any value of

is sufficient for this purpose.

Algorithms and implementations

The maximum-weight matching problem is solvable in polynomial time. Well-known algorithms include:

Other algorithms are reviewed by Duan and Pettie. Their work also proposes an approximation algorithm for general graphs that runs in linear time for any fixed error bound.

Efficient implementations are available in several software libraries, including NetworkX, LEDA, and the LEMON graph library.

Applications

Maximum-weight matchings (and their maximum cardinality variants) arise in a wide range of optimization settings.

  • Maximum cardinality minimum cost matchings are used in the approximation algorithm of Christofides for the traveling salesman problem. In problem instances where the edge weights form a metric space, this algorithm guarantees solution costs that are no more than 50% worse than the optimal cost.

  • Problems that involve assigning resources to entities can be modelled as maximum-weight matching problems on bipartite graphs, with edge weights reflecting the desirability of particular assignments. Examples include assigning workers to tasks, blood samples to patients, taxis to waiting customers, and sellers to buyers.

  • Maximum cardinality minimum cost matchings are used for solving several types of packing problem; particularly those that require optimal sequences of items to be identified.

  • In bioinformatics, the maximum-weight matching problem is used in analysing protein–protein interaction. Here, protein interactions within an organism are modelled as an edge-weighted graph, with vertices representing individual proteins and edge weights representing the confidence of their interactions being biologically relevant. The goal is to identify densely connected subgraphs within the graph, as these are likely to correspond to stable protein complexes that function as a unit within cells.

  • Maximum cardinality minimum cost matchings are used when solving the Chinese postman problem, which involves finding a minimum weight walk that visits every edge of an edge-weighted graph at least once.

See also

References