Near-optimal approximation algorithm for simultaneous Max-Cut

MaRDI QIDQ4607982zbMATH OpenFDO

Authors Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thimvenkatachari

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1801.04497, http://dl.acm.org/citation.cfm?id=3175398

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Cited in

(9)

• Simultaneous max-cut is harder to approximate than max-cut
• scientific article; zbMATH DE number 5232308 (Why is no real title available?)
• scientific article; zbMATH DE number 18532 (Why is no real title available?)
• Approximating graph-constrained max-cut
• Streaming Lower Bounds for Approximating MAX-CUT
• A discrete dynamic convexized method for the max-cut problem
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Socially fair network design via iterative rounding

This page was built for publication: Near-optimal approximation algorithm for simultaneous Max-Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607982)