The Exact Bipartite Matching Polytope Has Exponential Extension Complexity.

Xinrui Jia Ola Svensson Weiqiang Yuan

Published in: SODA (2023)

Keyphrases

bipartite matching
maximum weight
minimum cost flow
bayesian networks
worst case
knapsack problem
stable set
computational complexity
greedy algorithm
weighted graph
lattice points