Semidefinite relaxations for partitioning, assignment and ordering problems

Semidefinite relaxations for partitioning, assignment and ordering problems

0.00 Avg rating0 Votes
Article ID: iaor20162268
Volume: 240
Issue: 1
Start Page Number: 119
End Page Number: 140
Publication Date: May 2016
Journal: Annals of Operations Research
Authors:
Keywords: heuristics, programming: assignment
Abstract:

Semidefinite optimization is a strong tool in the study of NP‐hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey‐type article is meant as an introduction for a non‐expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.

Reviews

Required fields are marked *. Your email address will not be published.