A comparison of the Delsarte and Lovász bounds
From MaRDI portal
Publication:3888960
DOI10.1109/TIT.1979.1056072zbMath0444.94009OpenAlexW2114189119MaRDI QIDQ3888960
No author found.
Publication date: 1979
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/tit.1979.1056072
Delsarte's linear programming boundcliques in association schemesLovasz's theta-function boundShannon capacity of a graph
Related Items (99)
Capacities: From information theory to extremal set theory ⋮ Algebras, graphs and thetas ⋮ On standard quadratic programs with exact and inexact doubly nonnegative relaxations ⋮ Matrix Relaxations in Combinatorial Optimization ⋮ Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems ⋮ Mathematical Programming Models and Exact Algorithms ⋮ Tightening a copositive relaxation for standard quadratic optimization problems ⋮ Symmetry in Turán sums of squares polynomials from flag algebras ⋮ Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software ⋮ Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone ⋮ Copositive programming motivated bounds on the stability and the chromatic numbers ⋮ Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem ⋮ Copositivity cuts for improving SDP bounds on the clique number ⋮ A note on the stability number of an orthogonality graph ⋮ A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Semidefinite programming in combinatorial optimization ⋮ Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ Strengthened semidefinite programming bounds for codes ⋮ On product of association schemes and Shannon capacity ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ A characterization of Delsarte's linear programming bound as a ratio bound ⋮ Semidefinite bounds for the stability number of a graph via sums of squares of polynomials ⋮ Universal completability, least eigenvalue frameworks, and vector colorings ⋮ Sabidussi versus Hedetniemi for three variations of the chromatic number ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ A recursive Lovász theta number for simplex-avoiding sets ⋮ A semidefinite programming approach to a cross-intersection problem with measures ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs ⋮ Dimension reduction for semidefinite programs via Jordan algebras ⋮ Semidefinite programming bounds for binary codes from a split Terwilliger algebra ⋮ Semidefinite programming and its applications to NP problems ⋮ A Sum of Squares Characterization of Perfect Graphs ⋮ Graph homomorphisms via vector colorings ⋮ Vector coloring the categorical product of graphs ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Graph isomorphism: physical resources, optimization models, and algebraic characterizations ⋮ On Integrality in Semidefinite Programming for Discrete Optimization ⋮ Approximation of the Shannon capacity via matrix cone programming ⋮ Copositive optimization -- recent developments and applications ⋮ New eigenvalue bound for the fractional chromatic number ⋮ An efficiently computable subgraph pattern support measure: counting independent observations ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ Spectral bounds for the independence ratio and the chromatic number of an operator ⋮ Homomorphisms of strongly regular graphs ⋮ Chromatic Gallai identities operating on Lovász number ⋮ New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability ⋮ A polynomial time constraint-reduced algorithm for semidefinite optimization problems ⋮ Optimizing Hypergraph-Based Polynomials Modeling Job-Occupancy in Queuing with Redundancy Scheduling ⋮ A New Approach to the Stable Set Problem Based on Ellipsoids ⋮ Improving ADMMs for solving doubly nonnegative programs through dual factorization ⋮ The inertia bound is far from tight ⋮ Orthonormal representations, vector chromatic number, and extension complexity ⋮ On metric properties of maps between Hamming spaces and related graph homomorphisms ⋮ A new branch-and-bound algorithm for standard quadratic programming problems ⋮ A cross-intersection theorem for vector spaces based on semidefinite programming ⋮ A new property of the Lovász number and duality relations between graph parameters ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Optimization over structured subsets of positive semidefinite matrices via column generation ⋮ On the Lovász theta function and some variants ⋮ Semidefinite programming for discrete optimization and matrix completion problems ⋮ Quadratic factorization heuristics for copositive programming ⋮ Exploring the relationship between max-cut and stable set relaxations ⋮ Applications of Ramsey theory ⋮ Bounds on permutation codes of distance four ⋮ Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring ⋮ Reduction of truss topology optimization ⋮ Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Gap, cosum and product properties of the θ′ bound on the clique number ⋮ Convex Relaxations and Integrality Gaps ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ On different versions of the exact subgraph hierarchy for the stable set problem ⋮ Simple ingredients leading to very efficient heuristics for the maximum clique problem ⋮ A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations ⋮ On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs ⋮ Semidefinite programming bounds for Lee codes ⋮ Commutative association schemes ⋮ Role of redundant constraints for improving dual bounds in polynomial optimization problems ⋮ Exploiting group symmetry in truss topology optimization ⋮ Orthogonal representations over finite fields and the chromatic number of graphs ⋮ Exploiting special structure in semidefinite programming: a survey of theory and applications ⋮ On upper bounding Shannon capacity of graph through generalized conic programming ⋮ Lower bounds for measurable chromatic numbers ⋮ Spectral characterizations of the Lovász number and the Delsarte number of a graph ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming ⋮ D.C. versus copositive bounds for standard QP ⋮ Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory ⋮ Completely positive reformulations for polynomial optimization ⋮ A semidefinite programming hierarchy for packing problems in discrete geometry ⋮ Exploiting symmetry in copositive programs via semidefinite hierarchies ⋮ The density of sets avoiding distance 1 in Euclidean space ⋮ Complete positivity and distance-avoiding sets
This page was built for publication: A comparison of the Delsarte and Lovász bounds
