)-approximation for planar sparsest cut.
Vincent Cohen-AddadAnupam GuptaPhilip N. KleinJason LiPublished in: STOC (2021)
Keyphrases
- integrality gap
- linear programming relaxation
- planar graphs
- approximation algorithms
- lower bound
- linear program
- closed form
- relative error
- arbitrarily close
- error bounds
- approximation error
- np hard
- approximation schemes
- real time
- curved surfaces
- database
- valid inequalities
- linear programming
- lp relaxation
- approximation methods
- low degree
- image sequences