Improved Approximation Algorithms for Hitting 3-Vertex Paths.

Samuel Fiorini Gwenaël Joret Oliver Schaudt

Published in: IPCO (2016)

Keyphrases

approximation algorithms
undirected graph
disjoint paths
np hard
special case
vertex cover

minimum cost
worst case
network design problem
randomized algorithms
facility location problem
exact algorithms

np hardness
approximation ratio
open shop
primal dual
approximation schemes
directed graph

constant factor
objective function
set cover
combinatorial auctions
theoretical analysis
branch and bound