Promotie O. Kuryatnikova

The PhD dissertation proposes tractable linear and semidefinite relaxations for optimization problems that are hard to solve and approximate, such as polynomial or copositive problems. To do this, we exploit the structure and inherent symmetry of these problems. The thesis consists of five essays devoted to distinct problems. First, we consider the kissing number problem. The kissing number is the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, in n-dimensional space. In chapter two we construct a new hierarchy of upper bounds on the kissing number. To implement the hierarchy, in chapter three we propose two generalizations of Schoenberg's theorem on positive definite kernels. In the fourth chapter, we derive new certificates of non-negativity of polynomials on generic sets defined by polynomial equalities and inequalities. These certificates are based on copositive polynomials and allow obtaining new upper and lower bounds for polynomial optimization problems. In chapter five, for any given graph we look for the largest  k-colorable subgraph; that is, the induced subgraph that can be colored in k colors such that no two adjacent vertices have the same color. We obtain several new semidefinite programming relaxations to this problem. In the final sixth chapter, we consider the problem of allocating tasks to unrelated parallel selfish machines to minimize the time to complete all the tasks. For this problem, we suggest new upper and lower bounds on the best approximation ratio of a class of truthful task allocation algorithms.

Olga Kuryatnikova (Ryazan, Russia, 1989) received her Bachelor’s degree in Economics from Lomonosov Moscow State University in 2010 and Master's degree in Economics from Higher School of Economics in 2012. In 2015, she obtained Research Master's degree in Operations Research from Tilburg University and became a PhD candidate at Tilburg University. During the PhD period, she spent three weeks at Lehigh University as a visiting scholar. In October 2019, Olga joined the University of Western Ontario as a Postdoctoral Fellow.

• Locatie: Cobbenhagen building, Aula (toegang via Koopmans building)
• Promotor: prof. dr. ir. R. Sotirov
• Copromotores: dr. J.C. Vera Lizcano, dr. L.F. Zuluagua