Outward rotations

Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. We present a tool, outward rotations, for enhancing the performance of several semidefinite programming based approximation algorithms. Using outward rotations, we obtain an approximation algorithm for MAX CUT that, in many interesting cases, performs better than the algorithm of Goemans and Williamson. We also obtain an improved approximation algorithm for MAX NAE-f3g-SAT. Finally, we provide some evidence that outward rotations can also be used to obtain improved approximation algorithms for MAX NAE-SAT and MAX SAT. 1 Introduction MAX CUT is perhaps the simplest and most natural APX-complete constraint satisfaction problem (see, e.g., [AL97]). There are various simple ways of obtaining a performance guarantee of 1/2 for the problem. One of them, for example, is just choosing a random cut. No performance guarantee better than 1/2 was known for the problem until Goemans and Williamson [GW95], in a major breakthrough, used semidefinite programming to obtain an approximation algorithm ...

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 33 articles )

Showing results 1 to 20 of 33.
Sorted by year (citations)

1 2 next

  1. Xian, Aiyong; Zhu, Kaiyuan; Zhu, Daming; Pu, Lianrong: Local search to approximate MAX NAE-$k$-sat tightly (2015)
  2. d’Aspremont, Alexandre; Bach, Francis; El Ghaoui, Laurent: Approximation bounds for sparse principal component analysis (2014)
  3. Nederlof, Jesper; van Rooij, Johan M.M.; van Dijk, Thomas C.: Inclusion/exclusion meets measure and conquer (2014)
  4. Xu, BaoGang; Yu, XingXing; Zhang, XiaoYan; Zhang, Zan-Bo: An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance (2014)
  5. Xu, Zi; Du, Donglei; Xu, Dachuan: Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems (2014)
  6. Feige, Uriel; Immorlica, Nicole; Mirrokni, Vahab S.; Nazerzadeh, Hamid: PASS approximation: a framework for analyzing and designing heuristics (2013)
  7. Kim, Eun Jung; Williams, Ryan: Improved parameterized algorithms for above average constraint satisfaction (2012)
  8. Ling, Ai-fan; Xu, Cheng-xian: A new discrete filled function method for solving large scale max-cut problems (2012)
  9. Wu, Z.Y.; Li, G.Q.; Quan, J.: Global optimality conditions and optimization methods for quadratic integer programming problems (2011)
  10. Ling, Aifan; Tang, Le; Xu, Chengxian: Approximation algorithms for MAX RES CUT with limited unbalanced constraints (2010)
  11. Chen, Jianer; Lu, Songjian: Improved parameterized set splitting algorithms: A Probabilistic approach (2009)
  12. Ling, Ai-Fan; Xu, Cheng-Xian; Xu, Feng-Min: A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems (2009)
  13. Anjos, Miguel F.: An extended semidefinite relaxation for satisfiability (2008)
  14. Ling, Ai-Fan; Xu, Cheng-Xian; Xu, Feng-Min: A discrete filled function algorithm for approximate global solutions of max-cut problems (2008)
  15. Chen, Jianer; Lu, Songjian: Improved algorithms for weighted and unweighted set splitting problems (2007)
  16. Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (2007)
  17. Xu, Da-chuan; Zhang, Shu-zhong: Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation (2007)
  18. Asano, Takao: An improved analysis of Goemans and Williamson’s LP-relaxation for MAX SAT (2006)
  19. Alperin, Hernán; Nowak, Ivo: Lagrangian smoothing heuristics for Max-cut (2005)
  20. Anjos, Miguel F.: An improved semidefinite programming relaxation for the satisfiability problem (2005)

1 2 next