Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.
Lijie ChenGillat KolDmitry ParamonovRaghuvansh R. SaxenaZhao SongHuacheng YuPublished in: SODA (2023)
Keyphrases
- lower bound
- max cut
- closed form
- optimal solution
- np hard
- min sum
- upper bound
- worst case
- branch and bound algorithm
- objective function
- approximation algorithms
- branch and bound
- linear programming relaxation
- dynamic programming
- bayesian networks
- np complete
- minimum cost
- greedy heuristic
- planar graphs
- np complete problems
- special case