Derandomizing Approximation Algorithms Based on Semidefinite Programming

DOI10.1137/S0097539796309326MaRDI QIDQ4268812zbMATH OpenFDO

Authors H. Ramesh, Sanjeev Mahajan

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539796309326

zbMATH Keywords

approximation algorithmderandomizationNP-hardsemidefinite programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Algorithms and Data Structures
• scientific article; zbMATH DE number 1256751

Cited in

(16)

• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Deterministic discrepancy minimization
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• On fractional cut covers
• Sharp spectral bounds of several graph parameters using eigenvector norms
• scientific article; zbMATH DE number 1163722 (Why is no real title available?)
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• Deterministic APSP, Orthogonal Vectors, and More
• Quantum annealing versus digital computing. An experimental comparison
• Maximum cut parameterized by crossing number
• Technical note: Assortment optimization with small consideration sets
• Algorithms and Data Structures
• A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem
• Fault tolerant max-cut

This page was built for publication: Derandomizing Approximation Algorithms Based on Semidefinite Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268812)