Approximating the independence number via the \(\vartheta\)-function
From MaRDI portal
Publication:1380939
DOI10.1007/BF01581168zbMath0895.90169OpenAlexW2011869755MaRDI QIDQ1380939
Publication date: 22 April 1998
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01581168
Related Items
Maximum cliques in graphs with small intersection number and random intersection graphs, Complexity of approximating bounded variants of optimization problems, A heuristic for the stability number of a graph based on convex quadratic programming and tabu search, On a restricted cross-intersection problem, Semidefinite programming in combinatorial optimization, Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014., Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, On the Lovász Theta Function for Independent Sets in Sparse Graphs, Independence and matching numbers of unicyclic graphs from null space, A quantitative version of Steinhaus' theorem for compact, connected, rank-one symmetric spaces, Finding any given 2‐factor in sparse pseudorandom graphs efficiently, Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs, Making an H $H$‐free graph k $k$‐colorable, Local orthogonality dimension, New results for MaxCut in H$H$‐free graphs, Null decomposition of unicyclic graphs, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, A note on pseudorandom Ramsey graphs, Unnamed Item, A Sequence of Triangle-Free Pseudorandom Graphs, Orthonormal representations of \(H\)-free graphs, The Approximability of Assortment Optimization Under Ranking Preferences, Extremal results in sparse pseudorandom graphs, Lovász, Vectors, Graphs and Codes, Extremal results for odd cycles in sparse pseudorandom graphs, Near-perfect clique-factors in sparse pseudorandom graphs, Semidefinite programming and combinatorial optimization, Unnamed Item, On Constant Time Approximation of Parameters of Bounded Degree Graphs, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, On linear and semidefinite programming relaxations for hypergraph matching, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Near-perfect clique-factors in sparse pseudorandom graphs, Convex Relaxations and Integrality Gaps, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Deciding \(k\)-colorability in expected polynomial time, On approximation of max-vertex-cover, Ramsey numbers involving an odd cycle and large complete graphs in three colors, Heuristics for semirandom graph problems
Cites Work
- A better performance guarantee for approximate graph coloring
- The ellipsoid method and its consequences in combinatorial optimization
- On the complexity of approximating the independent set problem
- A note on Euclidean Ramsey theory and a construction of Bourgain
- Approximating maximum independent sets by excluding subgraphs
- A still better performance guarantee for approximate graph coloring
- The sandwich theorem
- Explicit Ramsey graphs and orthonormal labelings
- On the Shannon capacity of a graph
- Randomized graph products, chromatic numbers, and Lovasz j-function
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
