A 2-approximation for the bounded treewidth sparsest cut problem in sfFPT Time.

Vincent Cohen-Addad Tobias Mömke Victor Verdugo

Published in: Math. Program. (2024)

Keyphrases

bounded treewidth
integrality gap
np complete
linear programming relaxation
decision problems
highly parallelizable
conjunctive queries
boolean functions
approximation algorithms
lower bound
tractable cases
databases
closed form
fixed parameter tractable
integrity constraints
special case
machine learning