On upper bounding Shannon capacity of graph through generalized conic programming

DOI10.1007/S11590-019-01436-7MaRDI QIDQ2329653zbMATH OpenOpenAlexWikidataFDO

Authors Yingjie Bi, Ao Tang

Publication date 18 October 2019

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.08005

zbMATH Keywords

conic programmingShannon capacity of graphsum-of-squares optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: The Shannon capacity of a graph is an important graph invariant in information theory that is extremely difficult to compute. The Lovasz number, which is based on semidefinite programming relaxation, is a well-known upper bound for the Shannon capacity. To improve this upper bound, previous researches tried to generalize the Lovasz number using the ideas from the sum-of-squares optimization. In this paper, we consider the possibility of developing general conic programming upper bounds for the Shannon capacity, which include the previous attempts as special cases, and show that it is impossible to find better upper bounds for the Shannon capacity along this way.

Recommendations

• A bound on the Shannon capacity via a linear programming variation
• On the Shannon capacity of a graph
• New lower bounds for the Shannon capacity of odd cycles
• The Shannon capacity of a union
• scientific article; zbMATH DE number 2197920

Cites work

• A comparison of the Delsarte and Lovász bounds
• Approximation of the stability number of a graph via copositive programming
• Copositive programming motivated bounds on the stability and the chromatic numbers
• New lower bound on the Shannon capacity of \(C_7\) from circular graphs
• On the Shannon capacity of a graph
• Product Rules in Semidefinite Programming

Cited in

(3)

• New lower bound on the Shannon capacity of \(C_7\) from circular graphs
• A bound on the Shannon capacity via a linear programming variation
• Approximation of the Shannon capacity via matrix cone programming

This page was built for publication: On upper bounding Shannon capacity of graph through generalized conic programming

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