Optimization Hierarchies For Distance-Avoiding Sets In Compact Spaces
Bram Bekker (TU Delft - Discrete Mathematics and Optimization)
Olga Kuryatnikova (Erasmus School of Economics)
Fernando Mário de Oliveira Filho (TU Delft - Discrete Mathematics and Optimization)
Juan C. Vera (Tilburg University)
More Info
expand_more
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.
Abstract
Witsenhausen’s problem asks for the maximum fraction αn of the (n − 1)-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. The best upper bounds for αn are given by extensions of the Lovász theta number. In this paper, optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, are extended to Witsenhausen’s problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds for αn in low dimensions.
Files
File under embargo until 20-04-2026