Lecturer
Prof. Dr. Frank Vallentin
Teaching assistants
M.Sc. Maria Dostert, M.Sc. Jan Rolfes
Summary
It will be shown how to use semidefinite optimization in discrete geometry. Covered topics will include: Finding upper bounds for geometric packing problems, constructing optimal lattice sphere coverings, and computing low-distortion embeddings of finite metric spaces into Euclidean spaces.
Problem Sheets
Sheet 1: Conic optimization
Sheet 2: Embeddings
Sheet 3: Coverings
Sheet 4: Packings
Software
B. Borchers – CSDP Solver
A. Garber, A. Schürmann, F. Vallentin – scc (secondary cone cruiser)
Literature
General:
M. Laurent, F. Vallentin – Semidefinite Optimization, 2012
Conic optimization:
A. Nemirovski – Advances in convex optimization: conic programming, 2007
D. de Laat – A ten page introduction to conic optimization, 2015
Embeddings:
S. Hoory, N. Linial, A. Wigderson – Expander graphs and their applications, 2006
J. Matousek – Lectures on Discrete Geometry (Chapter 15), 2005
F. Vallentin – Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces, 2008
Coverings:
A. Schürmann, F. Vallentin – Computational Approaches to Lattice Packing and Covering Problems, 2006
M. Dutour-Sikiric, A. Schürmann, F. Vallentin – A generalization of Voronoi’s reduction theory and its application, 2008
M. Dutour-Sikiric, A. Schürmann, F. Vallentin – Inhomogeneous extreme forms, 2012
Packings:
P.E.B. DeCorte, D. de Laat, F. Vallentin – Fourier analysis on finite groups and the Lovász theta-number of Cayley graphs, 2014
F.M. de Oliveira Filho, F. Vallentin – Mathematical optimization for packing problems, 2014