Derandomizing Approximation Algorithms Based on Semidefinite Programming

DOI10.1137/S0097539796309326zbMath0928.68055MaRDI QIDQ4268812

H. Ramesh, Sanjeev Mahajan

Publication date: 28 October 1999

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

zbMATH Keywords

semidefinite programmingapproximation algorithmNP-hardderandomization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ 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 ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ Quantum Annealing versus Digital Computing ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Technical Note—Assortment Optimization with Small Consideration Sets ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ Deterministic discrepancy minimization ⋮ On fractional cut covers ⋮ Approximating a generalization of MAX 2SAT and MIN 2SAT

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