Short summary: This course will present the ideas and techniques behind constructing samples for a variety of geometric configurations. We will then present some recent algorithmic applications to geometric optimization problems. The course will start with combinatorics of geometric set systems (e.g., VC-dimension, shallow-cell complexity), leading to packing analogues for combinatorial set systems. These combinatorial bounds will then be used to construct small-sized samples of geometric configurations (e.g., epsilon-nets, epsilon-approximations, relative approximations). Finally, we will see how this can be used to construct coresets for optimization problems (e.g., k-means, projective clustering) using the technique of Feldman-Langberg-Schulman.
Organized by MTA-ELTE CoGe.
When: 2019 February 11-15, each day from 2 pm.
Where: ELTE Déli Tömb, room 3-607.
Credits: ELTE PhD and MSc students can take the course in Neptun to receive credits.