On an SDP relaxation for kissing number

Jon Lee (1) , Leo Liberti (2)

1 Department of Mathematical Sciences, TJ Watson
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

We demonstrate that an earlier semidefinite-programming relaxation for the kissing-number problem cannot provide good upper bounds. Furthermore , we show the existence of an optimal solution for this relaxation that cannot be used as a basis for establishing a good lower bound.

Domaines: Recherche opérationnelle [math.OC]

Jon Lee, Leo Liberti. On an SDP relaxation for kissing number. Optimization Letters, 2020, 14 (2), pp.417-422. ⟨10.1007/s11590-018-1239-9⟩. ⟨hal-02869223⟩