A characterization of Delsarte's linear programming bound as a ratio bound

DOI10.1016/J.LAA.2006.10.009MaRDI QIDQ876308zbMATH OpenOpenAlexWikidataFDO

Authors Carlos J. Luz

Publication date 18 April 2007

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2006.10.009

zbMATH Keywords

quadratic programmingcombinatorial optimizationgraph theoryassociation schememaximum stable setDelsarte's linear programming bound

Mathematics Subject Classification ID

Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Linear programming (90C05) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Association schemes, strongly regular graphs (05E30)

Recommendations

• A subexponential bound for linear programming
• On the optimum of Delsarte's linear program
• A combinatorial bound for linear programming and related problems
• Rigorous Lower and Upper Bounds in Linear Programming
• Bounding duality gap for separable problems with linear constraints
• Boundedness relations in linear semi-infinite programming
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Linear programming bounds
• Bounds for the solution set of linear complementarity problems
• A review of computation of mathematically rigorous bounds on optima of linear programs

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3528270 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3634289 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A comparison of the Delsarte and Lovász bounds
• A note on the stability number of an orthogonality graph
• An upper bound on the independence number of a graph computable in polynomial-time
• Approximation of the stability number of a graph via copositive programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Geometric algorithms and combinatorial optimization
• Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
• Matrix Analysis
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On the Shannon capacity of a graph
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(8)

• A note on Erdős-Ko-Rado sets of generators in Hermitian polar spaces
• Cross-intersecting Erdős-Ko-Rado sets in finite classical polar spaces
• Optimal and extremal graphical designs on regular graphs associated with classical parameters
• Linear programming bounds for regular graphs
• A comparison of the Delsarte and Lovász bounds
• An Erdős-Ko-Rado theorem for finite classical polar spaces
• A note on the stability number of an orthogonality graph
• Hoffman's ratio bound

This page was built for publication: A characterization of Delsarte's linear programming bound as a ratio bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876308)