Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- 1 November 1995
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 42 (6), 1115-1145
- https://doi.org/10.1145/227683.227684
Abstract
No abstract availableThis publication has 30 references indexed in Scilit:
- Solving the max-cut problem using eigenvaluesDiscrete Applied Mathematics, 1995
- On the Approximation of Maximum SatisfiabilityJournal of Algorithms, 1994
- Combinatorial Properties and the Complexity of a Max-cut ApproximationEuropean Journal of Combinatorics, 1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Approximation and intractability results for the maximum cut problem and its variantsIEEE Transactions on Computers, 1991
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability ProblemCanadian Journal of Mathematics, 1982
- How well can a graph be n-colored?Discrete Mathematics, 1981
- A linear-time approximation algorithm for the weighted vertex cover problemJournal of Algorithms, 1981
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976