Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. (English) Zbl 1345.90064
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 679-687 (1999).
MSC:
| 90C22 | Semidefinite programming |
| 05C40 | Connectivity |
| 68W25 | Approximation algorithms |
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Citations:
Zbl 0885.68088Software:
Outward rotationsReferences:
| [1] | G. Andersson and L. Engebretsen. Better approximation algorithms for SET SPLITTING and NoT-ALL-EQUAL SAT. Information Processing Letters, 65:305-311, 1998.]] 10.1016/S0020-0190(98)00021-0 · Zbl 1338.68286 |
| [2] | S. Arora and C. Lund. Hardness of approximation. In D. Hochbaum, editor, Approximation algorithms for NP-hard problems, pages 399-446. PWS Publishing Company, 1997.]] |
| [3] | N. Alon and B. Sudakov. Bipartite subgraphs and the smallest eigenvalue. Manuscript, 1998.]] · Zbl 0945.05041 |
| [4] | T. Asano. Approximation algorithms for MAX SAT: Yannakakis vs. Goemans- Williamson. In Proceedings of the 3nd Israel Symposium on Theory and Computing Systems, Ramat Gan, Israel, pages 24-37, 1997.]] |
| [5] | N. Alon, B. Sudakov, and U. Zwick. Work in progress, 1998.]] |
| [6] | U. Feige and M.X. Goemans. Approximating the value of two prover proof systems, with applications to MAX-2SAT and MAX-DICUT. In Proceedings of the 3nd Israel Symposium on Theory and Computing Systems, Tel A viv, Israel, pages 182-189, 1995.]] |
| [7] | M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115-1145, 1995.]] 10.1145/227683.227684 · Zbl 0885.68088 |
| [8] | J. H tad. Some optimal inapproximability results. In Proceedings of the 28th Annual A CM Symposium on Theory of Computing, El Paso, Texas, pages 1-10, 1997. Full version available as E-CCC Report number TR97- 037.]] 10.1145/258533.258536 · Zbl 0963.68193 |
| [9] | E. Halperin and U. Zwick. Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs. In Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization, Graz, Austria, 1999. To appear.]] · Zbl 0948.90154 |
| [10] | H. Karloff. How good is the Goemans- Williamson MAX CUT algorithm? In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, pages 427-434, 1996.]] 10.1145/237814.237990 · Zbl 0922.68068 |
| [11] | V. Kann, J. Lagergren, and A. Panconesi. Approximability of maximum splitting of ksets and some other APX-complete problems. Information Processing Letters, 58:105-110, 1996.]] 10.1016/0020-0190(96)00046-4 · Zbl 0998.90525 |
| [12] | H. Karloff and U. Zwick. A 7/8-approximation algorithm for MAX 3SAT? In Proceedings of the 38rd Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, Florida, pages 406-415, 1997.]] |
| [13] | S. Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In Proceedings of the 36rd Annual IEEE Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, pages 162-169, 1995.]] · Zbl 0938.68915 |
| [14] | Y.E. Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 9:141-160, 1998.]] · Zbl 0904.90136 |
| [15] | L. Trevisan. Approximating satisfiable satisfiability problems. In Proceedings of the 5th European Symposium on Algorithms, Graz, Austria, 1997. 472-485.]] · Zbl 1477.68539 |
| [16] | M. Yannakakis. On the approximation of maximum satisfiability. Journal of Algorithms, 7:475-502, 1994.]] 10.1006/jagm.1994.1045 · Zbl 0820.68056 |
| [17] | U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th Annual A CM-SIAM Symposium on Discrete Algorithms, San Francisco, California, pages 201-210, 1998.]] · Zbl 0930.68142 |
| [18] | U. Zwick. Finding almost-satisfying assignments. In Proceedings of the 29th Annual A CM Symposium on Theory of Computing, Dallas, Texas, pages 551-560, 1998.]] 10.1145/276698.276869 · Zbl 1028.68066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
