A Local Constant Factor MDS Approximation for Bounded Genus Graphs.

Saeed Akhoondian Amiri Stefan Schmid Sebastian Siebertz

Published in: PODC (2016)

Keyphrases

constant factor
approximation algorithms
approximation guarantees
lower bound
worst case
upper bound
constant factor approximation algorithm
greedy algorithm
approximation ratio
special case
np hard
sample complexity
linear programming relaxation
dynamic programming
cross validation