Directly to content
  1. Publishing |
  2. Search |
  3. Browse |
  4. Recent items rss |
  5. Open Access |
  6. Jur. Issues |
  7. DeutschClear Cookie - decide language by browser settings

Representations of Partition Problems and the Method of Moments

Silvestri, Francesco

PDF, English - main document
Download (1MB) | Terms of use

Citation of documents: Please do not cite the URL that is displayed in your browser location input, instead use the DOI, URN or the persistent URL below, as we can guarantee their long-time accessibility.


The thesis follows two main goals. The first is to formulate, explain and link representations of partitions that can be used to model partition problems. The second is to use the method of moments, an approach from polynomial optimization, to bound the global optima of the corresponding partition problems by constructing convex relaxations of these representations. For problems like Euclidean k-clustering, this is a stark contrast to their usual treatment, which mostly involves heuristics that are content with local optima. Since the method of moments results in a convex approach, the focus lies on finding and exploiting representations that lack a non-trivial symmetry-invariant solution space in order to be able to round the relaxations to feasible solutions.

The representations considered in the thesis are assignment matrices, partition matrices, projection matrices and simplicial covers for a generalized version of Euclidean k-clustering. Connections and transformations between the matrix classes are established and compared to the literature, and it is explicitly shown how partition matrices arise naturally from assignment matrices through the method of moments.

Using projection matrices, we are able to give a new formulation of the colouring number, and the resulting relaxations from the method of moments are compared to the Lovász theta number. We characterize under which circumstances the relaxations agree and explain when they do not, indicating our first main result that in this case, relaxing binary matrix entries yields better results than relaxing binary eigenvalues.

The final part of the thesis is devoted to what we call the affine Euclidean k-clustering problem, which is a more general version of the Euclidean k-clustering problem. As our second main result of the thesis, we introduce a new method for this challenging problem, utilizing simplicial covers of the feasible region to formulate unique representations of the optimal solutions of the underlying problem. In contrast to applying the method of moments directly, applying it to our formulation yields a slower growth in size, better parallelizability and enables us to recover information that can be used for rounding, which is not possible for the standard formulation due to symmetry.

Item Type: Dissertation
Supervisor: Reinelt, Prof. Dr. Gerhard
Date of thesis defense: 18 October 2017
Date Deposited: 04 Dec 2017 10:43
Date: 2017
Faculties / Institutes: The Faculty of Mathematics and Computer Science > Department of Applied Mathematics
The Faculty of Mathematics and Computer Science > Department of Computer Science
Subjects: 510 Mathematics
Controlled Keywords: Semidefinite Optimierung, Nichtlineare Optimierung, Stabile-Mengen-Problem
About | FAQ | Contact | Imprint |
OA-LogoDINI certificate 2013Logo der Open-Archives-Initiative