Approximation of the Shannon Capacity Via Matrix Cone Programming

doi:10.1007/s40305-022-00408-6

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 875-889.doi: 10.1007/s40305-022-00408-6

Previous Articles Next Articles

Approximation of the Shannon Capacity Via Matrix Cone Programming

Shi-Tong Wu^1,2, 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

Received:2021-02-04 Revised:2022-02-18 Online:2023-12-30 Published:2023-12-26
Contact: Zhen-Nan Zhou, Shi-Tong Wu, Zhong-Yi Huang, Bo Bai E-mail:zhennan@bicmr.pku.edu.cn;wust20@mails.tsinghua.edu.cn;zhongyih@tsinghua.edu.cn;ee.bobbai@gmail.com
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11871297, 11871298, 12025104 and 12031013) and the Tsinghua University Initiative Scientific Research Program. Zhen-Nan Zhou was also partially supported by the National Key R&D Program of China (No. 2020YFA0712000).

Abstract

Abstract: 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.

Key words: Shannon capacity, Lovász number, Matrix cone programming, Weak product property

CLC Number:

Shi-Tong Wu, Zhen-Nan Zhou, Zhong-Yi Huang, Bo Bai. Approximation of the Shannon Capacity Via Matrix Cone Programming[J]. Journal of the Operations Research Society of China, 2023, 11(4): 875-889.

TrendMD

References

[1] Shannon, C.E.: The zero error capacity of a noisy channel. IRE Trans. Inform. Theory 2(3), 8-19 (1956)
[2] Alon, N., Lubetzky, E.: The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans. Inf. Theory 52(5), 2172-2176 (2006)
[3] Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1-7 (1979)
[4] Lovász, László.: Graphs and Geometry. American Society of Mathematics (2019) https://doi.org/10.1090/coll/065
[5] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim.n Methods Softw. 11(1), 625-653 (1999)
[6] Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3 - a MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1), 545-581 (1999)
[7] Sun, D., Toh, K.C., Yuan, Y., Zhao, X.Y.: SDPNAL+: a Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35(1), 87-115 (2020)
[8] Schrijver, A.: A Comparison of the Delsarte and Lovász Bounds. IEEE Trans. Inf. Theory 25(4), 425-429 (1979)
[9] De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875-892 (2002)
[10] Parrilo, P. A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and Optimization. Technical report, Massachusetts Institute of Technology (2000)
[11] Peña, J., Vera, J., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1), 87-105 (2007)
[12] Bomze, I.M., Frommlet, F., Locatelli, M.: Copositivity cuts for improving SDP bounds on the clique number. Math. Program. 124(1-2), 13-32 (2010)
[13] Bi, Y., Tang, A.: On upper bounding Shannon capacity of graph through generalized conic programming. Optim. Lett. 13(6), 1313-1323 (2019)
[14] Polak, S.C., Schrijver, A.: New lower bound on the Shannon capacity of C₇ from circular graphs. Inf. Process. Lett. 143(2), 37-40 (2019)
[15] Zhao, X.Y., Sun, D., Toh, K.C.: A newton-cg augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737-1765 (2010)
[16] Yang, L., Sun, D., Toh, K.C.: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331-366 (2015)
[17] Haemers, W.: On Some Problems of Lovasz Concerning the Shannon Capacity of a Graph. IEEE Trans. Inf. Theory 25(2), 231-232 (1979)
[18] Haemers, W.H.: An upper bound for the shannon capacity of a graph. Colloquia Math. Societatis Janos Bolyai 25, 267-272 (1978)
[19] Sihuang, H., Tamo, I., Shayevitz, O.: A bound on the shannon capacity via a linear programming variation. SIAM J. Discret. Math. 32(3), 2229-2241 (2018)

Approximation of the Shannon Capacity Via Matrix Cone Programming

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics

Comments

[1]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.
[2]	Feng-Min Wang, Jia-Jia Wang, Na Li, Yan-Jun Jiang, Shi-Cheng Li. A Cost-Sharing Scheme for the k-Level Facility Location Game with Penalties [J]. Journal of the Operations Research Society of China, 2022, 10(1): 173-182.
[3]	Xiao-Dan Jia, Bo Hou, Wen Liu. An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties [J]. Journal of the Operations Research Society of China, 2022, 10(1): 183-192.
[4]	Long-Cheng Liu, Han Gao, Chao Li. Inverse Maximum Flow Problem Under the Combination of the Weighted l₂ Norm and the Weighted Hamming Distance [J]. Journal of the Operations Research Society of China, 2021, 9(2): 465-474.
[5]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[6]	Jiang Hu, Xin Liu, Zai-Wen Wen, Ya-Xiang Yuan. A Brief Introduction to Manifold Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(2): 199-248.
[7]	Min Li, Dong-Lei Du, Da-Chuan Xu, Zhen-Ning Zhang. A Note on Submodularity Preserved Involving the Rank Functions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 399-407.
[8]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[9]	Yi-Jing Wang, Da-Chuan Xu, Yan-Jun Jiang, Dong-Mei Zhang. Minimizing Ratio of Monotone Non-submodular Functions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 449-459.
[10]	Long Wan, Jin-Jiang Yuan. Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems [J]. Journal of the Operations Research Society of China, 2019, 7(3): 485-500.
[11]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.