Approximation of the Shannon Capacity Via Matrix Cone Programming  

作　　者：Shi-Tong Wu Zhen-Nan Zhou Zhong-Yi Huang Bo Bai 

机构地区：[1]Department of Mathematical Sciences,Tsinghua University,Beijing,100084,China [2]Theory Lab,Central Research Institute,2012 Labs,Huawei Technologies Co.,Ltd.,Hong Kong,China [3]Beijing International Center for Mathematical Research,Peking University,Beijing,100871,China

出　　处：《Journal of the Operations Research Society of China》2023年第4期875-889,共15页中国运筹学会会刊（英文）

基　　金：supported by the National Natural Science Foundation of China(Nos.11871297,11871298,12025104 and 12031013);the Tsinghua University Initiative Scientific Research Program;supported by the National Key R&D Program of China(No.2020YFA0712000).

摘　　要：This paper proposes a novel formulation using the matrix cone programming to compute an upper bound of the Shannon capacity of graphs,which is theoretically superior to the Lovász number.To achieve this,a sequence of matrix cones is constructed by adding certain co-positive matrices to the positive semi-definite matrix cones during the matrix cone programming.We require the sequence of matrix cones to have the weak product property so that the improved result of the matrix cone programming remains an upper bound of the Shannon capacity.Our result shows that the existence of a sequence of suitable matrix cones with the weak product property is equivalent to the existence of a co-positive matrix with testable conditions.Finally,we give some concrete examples with special structures to verify the existence of the matrix cone sequence.

关 键 词：Shannon capacity Lovász number Matrix cone programming Weak product property 

分 类 号：O17[理学—数学]