Seminar: Nando Leijenhorst (TU Delft) and Artem Tsikiridis (CWI)

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Nando Leijenhorst (TU Delft) 

Title: Optimality and uniqueness of the D4 root system

Abstract:

The spherical code problem asks how to arrange N points on the unit sphere in dimension n such that the distance between the closest pair of points is maximized.

We prove that for 24 points in dimension 4, the D4 root system is the optimal configuration, by showing that it is the unique solution for the kissing number problem in dimension 4, up to isometry. For this we use a semidefinite programming relaxation of the second step of the Lasserre hierarchy for spherical codes, for which we obtain an exact optimal solution by rounding the numerical solution using the techniques of [Cohn, de Laat, Leijenhorst, 2024+].

In this talk, I will explain the steps needed to prove the result, including the main steps of the rounding procedure.

Joint work with David de Laat and Willem de Muinck Keizer (https://arxiv.org/abs/2404.18794).
The rounding procedure is joint work with Henry Cohn and David de Laat (https://arxiv.org/abs/2403.16874).

Video:

Slides:

Speaker: Artem Tsikiridis (CWI) 

Title: Pandora's Box Problem Over Time

Abstract:

The Pandora's Box problem models the search for the best alternative when evaluation is costly. In its simplest variant, a decision maker is presented with n boxes, each associated with a cost of inspection and a distribution over the reward hidden within. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive ordering, and obtains as utility the difference between the largest reward uncovered and the sum of the inspection costs. While this classic version of the problem is well understood (Weitzman 1979), recent years have seen a flourishing of the literature on variants of the problem. In this paper, we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e.g., as it might constrain the schedules of exploration and influence both costs and rewards. In the Pandora's Box Over Time problem, each box is characterized by time-dependent rewards and costs, and inspecting it might require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time, possibly differently for each box. Our main result is an efficient 21.3-approximation to the optimal strategy, which is NP-hard to compute in general. We further obtain improved results for the natural special cases where boxes have no processing time, or when costs and reward distributions do not depend on time (but rewards may deteriorate after inspecting).  

Joint work with Georgios Amanatidis, Federico Fusco and Rebecca Reiffenhäuser (https://arxiv.org/abs/2407.15261).  

Video:

Slides: