Approximation Algorithms for Flexible Graph Connectivity.

Sylvia C. Boyd Joseph Cheriyan Arash Haddadan Sharat Ibrahimpur

Published in: CoRR (2022)

Keyphrases

approximation algorithms
graph connectivity
np hard
special case
worst case
vertex cover
facility location problem

approximation ratio
approximation schemes
minimum cost
network design problem
constant factor
np hardness

randomized algorithms
combinatorial auctions
open shop
disjoint paths
set cover
primal dual

weighted graph
natural language
precedence constraints
undirected graph
linear programming
constant factor approximation