An exponential lower bound for cut sparsifiers in planar graphs.

Nikolai Karpov Marcin Pilipczuk Anna Zych-Pawlewicz

Published in: CoRR (2017)

Keyphrases

planar graphs
lower bound
upper bound
branch and bound
lower and upper bounds
objective function
np hard
partition function
branch and bound algorithm
optimal solution
worst case
minimum weight
upper and lower bounds
approximate inference
lagrangian relaxation
graphical models
belief propagation