On the Hardness of Approximating Multicut and Sparsest-Cut.

Shuchi Chawla Robert Krauthgamer Ravi Kumar Yuval Rabani D. Sivakumar

Published in: Comput. Complex. (2006)

Keyphrases

data sets
learning theory
rooted trees
information theoretic
real world
case study
computational complexity
phase transition
np complete
np hard
truth table
exact computation
mutual information
lower bound
machine learning
data mining
databases