Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover.

Published in: SOSA (2024)

Keyphrases

independent set
vertex cover
approximation algorithms
partial order
maximum weight
planar graphs
optimality criterion
precedence constraints
worst case
graphical models
piecewise linear
polynomial time approximation