A cutting plane approach to upper bounds on the kissing number

Bachelor thesis (2023)

Authors

N. Riemens Electrical Engineering, Mathematics and Computer Science

Contributors

F.M. de Oliveira Filho Discrete Mathematics and Optimization (mentor)
W.G.M. Groenevelt Analysis (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Noud Riemens
More Info
expand_more

Published Date

22-08-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Upper bounds for the kissing number can be written as a semidefinite program (SDP) through the Delsarte-Goethals-Seidel method for spherical codes. This thesis solves the resulting SDP with a cutting plane approach, in which a sequence of linear programs (LPs) is solved with the addition of linear constraints every round. We study the computational efficiency of dense and sparser cuts. Sparse cuts are obtained through a relation to the $k$-Sparse Principal Component Analysis problem. For the modest polynomial degrees considered, the dense and sparse methods show similar performance. Upper bounds are obtained through calculations in standard and where necessary quadruple precision. Lastly, it is shown that under a linear cutting plane approach the SDP is solved quicker if not every subsequent LP is solved till optimality.

Files

A_cutting_plane_approach_to_up... (pdf)
(pdf | 1.07 Mb)
Unknown license