scientific article
From MaRDI portal
Publication:3002764
DOI10.4086/toc.2006.v002a002zbMath1213.68306OpenAlexW1587123489MaRDI QIDQ3002764
Iannis Tourlakis, László Lovász, Sanjeev Arora, Béla Bollobás
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2006.v002a002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
linear programmingapproximation algorithmsvertex coverinapproximabilityNP-hard problemsintegrality gapslift-and-project
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Integrality gaps for strengthened linear relaxations of capacitated facility location, On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications, On the approximability of digraph ordering, Integrality gaps for colorful matchings, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Toward a model for backtracking and dynamic programming, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, A stronger model of dynamic programming algorithms, Unnamed Item, Convex Relaxations and Integrality Gaps, Semidefinite and linear programming integrality gaps for scheduling identical machines, Expanders with respect to Hadamard spaces and random graphs, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Sherali-adams strikes back, Strong and weak edges of a graph and linkages with the vertex cover problem, Priority algorithms for graph optimization problems, Unnamed Item, Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem
