Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  20 Sep 2019 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  978 90 5668 603 1 
Publication status  Published  2019 
Fingerprint
Cite this
}
The many faces of positivity to approximate structured optimization problems. / Kuryatnikova, Olga.
Tilburg : CentER, Center for Economic Research, 2019. 186 p.Research output: Thesis › Doctoral Thesis › Scientific
TY  THES
T1  The many faces of positivity to approximate structured optimization problems
AU  Kuryatnikova, Olga
N1  CentER Dissertation Series Volume: 602
PY  2019
Y1  2019
N2  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 nonoverlapping unit spheres that can simultaneously touch another unit sphere, in ndimensional 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 nonnegativity 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 kcolorable 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.
AB  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 nonoverlapping unit spheres that can simultaneously touch another unit sphere, in ndimensional 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 nonnegativity 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 kcolorable 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.
M3  Doctoral Thesis
SN  978 90 5668 603 1
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 