A comparison of the Delsarte and Lovász bounds
From MaRDI portal
Publication:3888960
DOI10.1109/TIT.1979.1056072zbMath0444.94009OpenAlexW2114189119MaRDI QIDQ3888960
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
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, 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, 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
