Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems

This publication has 10 references indexed in Scilit:

• Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
  2002
• 0.863-Approximation Algorithm for MAX DICUT
  2001
• The RPR 2 Rounding Technique for Semidefinite Programs
  Lecture Notes in Computer Science, 2001
• Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms
  SIAM Journal on Discrete Mathematics, 2001
• Bipartite Subgraphs and the Smallest Eigenvalue
  Combinatorics, Probability and Computing, 2000
• Gadgets, Approximation, and Linear Programming
  SIAM Journal on Computing, 2000
• How Good is the Goemans--Williamson MAX CUT Algorithm?
  SIAM Journal on Computing, 1999
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
  SIAM Journal on Computing, 1999
• Some optimal inapproximability results
  1997
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
  Journal of the ACM, 1995