Matching Is as Easy as Matrix Inversion

Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987). Matching Is as Easy as Matrix Inversion. Combinatorica, 105-113.

Type

Journal article

Intellectual base

Primary research

Year

1987

DOI

10.1007/bf02579206

Link

https://doi.org/10.1007/bf02579206

Cited by

1 citation across 1 artifact.

Domain-specific

• Isolation lemma
  • The isolation lemma states that if each element of an \(n\)-element ground set independently receives a weight uniformly from \(\{1,\ldots,N\}\), then any nonempty family of subsets has a unique minimum-weight member with probability at least \(1-n/N\).

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:0c1d5953abb4 · see in the full table