𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Derandomizing Approximation Algorithms Based on Semidefinite Programming

✍ Scribed by Mahajan, Sanjeev; Ramesh, H.

Book ID
118178203
Publisher
Society for Industrial and Applied Mathematics
Year
1999
Tongue
English
Weight
482 KB
Volume
28
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximation Algorithms and Semidefinit
Approximation Algorithms and Semidefinite Programming || Duality and Cone Programming
✍ GΓ€rtner, Bernd; Matousek, Jiri πŸ“‚ Article πŸ“… 2011 πŸ› Springer Berlin Heidelberg 🌐 German βš– 993 KB

Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexit

Approximation Algorithms for MAX 4-SAT a
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs
✍ Eran Halperin; Uri Zwick πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 188 KB

Karloff and Zwick obtained recently an optimal 7r8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7r8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinit