Approximation Algorithms and Semidefinite Programming

DOI10.1007/978-3-642-22015-9zbMath1257.90001OpenAlexW1540529426MaRDI QIDQ3094772

Bernd Gärtner, Ji{ří} Matoušek

Publication date: 26 October 2011

Full work available at URL: https://doi.org/10.1007/978-3-642-22015-9

zbMATH Keywords

semidefinite programminggraph theoryapproximation algorithmsapproximation ratiosemidefinite programming relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)

Related Items (34)

Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Bistable latch Ising machines ⋮ Approximating the weighted maximin dispersion problem over an \(\ell _p\)-ball: SDP relaxation is misleading ⋮ Regularity properties of non-negative sparsity sets ⋮ Incompatibility in general probabilistic theories, generalized spectrahedra, and tensor norms ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ Control of multi-scroll Chen system ⋮ A semidefinite programming approach to a cross-intersection problem with measures ⋮ Optimal arrangements of classical and quantum states with limited purity ⋮ The maximum measure of non-trivial 3-wise intersecting families ⋮ Graph isomorphism: physical resources, optimization models, and algebraic characterizations ⋮ Approximating projections by quantum operations ⋮ Polyhedral approximation of spectrahedral shadows via homogenization ⋮ Variational Gaussian approximation for Poisson data ⋮ An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound ⋮ A new proof for the existence of degree bounds for Putinar’s Positivstellensatz ⋮ Numerical algebraic geometry and semidefinite programming ⋮ Semidefinite relaxation for the total least squares problem with Tikhonov-like regularization ⋮ Tropical spectrahedra ⋮ The determinant bound for discrepancy is almost tight ⋮ Unnamed Item ⋮ Hyperbolic efficiency measurement: a conic programming approach ⋮ Application of facial reduction to H _∞ state feedback control problem ⋮ Tight Bounds on the Radius of Nonsingularity ⋮ Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming ⋮ The theta number of simplicial complexes ⋮ On Hazan's algorithm for symmetric programming problems ⋮ Three-monotone interpolation

This page was built for publication: Approximation Algorithms and Semidefinite Programming