Near-optimal approximation algorithm for simultaneous Max-Cut

zbMATH Open1403.68149arXiv1801.04497MaRDI QIDQ4607982FDOQ4607982

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

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

Mathematics Subject Classification ID

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

Cited In (9)

• Simultaneous max-cut is harder to approximate than max-cut
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)