Advanced search
Start date
Betweenand

Applications of Semidefinite Programming in Combinatorial Optimization

Grant number: 13/20740-9
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): January 01, 2014
Effective date (End): August 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Yoshiko Wakabayashi
Grantee:Marcel Kenji de Carli Silva
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM

Abstract

In this project we focus on the development of tools from Semidefinite Programming and Convex Analysis for applications in Combinatorial Optimization, aiming to generalize the approach from Polyhedral Combinatorics. We are interested on the facial structure of semidefinite relaxations for certain combinatorial problems and its correspondence with combinatorial properties of the problems at hand. As a byproduct, we hope to enhance our understanding about the real gain of semidefinite formulations that make them so tighter than linear formulations for certain problems, and potentially replicate this success in other problems.Most of the known results in this line of research revolves around the central object known as the theta body of a graph, from which one may define the Lovász theta function. The theory surrounding these objects is quite rich and elegant, and it also applies to the semidefinite program utilized by Goemans and Williamson in their famous approximation algorithm for the maximum cut problem. We describe certain research directions involving the facial structure of these objects and the corresponding optimality conditions, as well as broader avenues of research with the goal of determining the true power of semidefinite formulations in Combinatorial Optimization and otherwise.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
DE CARLI SILVA, MARCEL K.; TUNCEL, LEVENT. An axiomatic duality framework for the theta body and related convex corners. MATHEMATICAL PROGRAMMING, v. 162, n. 1-2, p. 283-323, MAR 2017. Web of Science Citations: 0.
DE CARLI SILVA, MARCEL K.; TUNCEL, LEVENT. VERTICES OF SPECTRAHEDRA ARISING FROM THE ELLIPTOPE, THE THETA BODY, AND THEIR RELATIVES. SIAM JOURNAL ON OPTIMIZATION, v. 25, n. 1, p. 295-316, 2015. Web of Science Citations: 2.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.