Approximation Algorithms for the Minimum Convex Partition Problem.

Christian Knauer Andreas Spillner

Published in: SWAT (2006)

Keyphrases

approximation algorithms
minimum cost
constant factor
np hard
special case
quadratic program
worst case

vertex cover
facility location problem
np hardness
network design problem
convex optimization
network flow
spanning tree

exact algorithms
open shop
set cover
precedence constraints
primal dual
undirected graph
polynomial time approximation

randomized algorithms
approximation schemes
disjoint paths
lower bound
min cut
convex hull
dynamic programming