Approximating Maximum Matching Requires Almost Quadratic Time.

Soheil Behnezhad Mohammad Roghani Aviad Rubinstein

Published in: STOC (2024)

Keyphrases

maximum matching
bipartite graph
stable set
objective function
special case
random walk
computational complexity
pairwise
machine learning
reinforcement learning
state space
heuristic search