Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

An axiomatic duality framework for the theta body and related convex corners

Texto completo
Autor(es):
de Carli Silva, Marcel K. ; Tuncel, Levent
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: MATHEMATICAL PROGRAMMING; v. 162, n. 1-2, p. 283-323, MAR 2017.
Citações Web of Science: 0
Resumo

Lovasz theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of ``Schur Lifting{''} of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl from 2010. (AU)

Processo FAPESP: 13/20740-9 - Aplicações de programação semidefinida em otimização combinatória
Beneficiário:Marcel Kenji de Carli Silva
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático