Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Notion of Total Dual Integrality for Convex, Semidefinite, and
  Extended Formulations   Total dual integrality is a powerful and unifying concept in polyhedral
combinatorics and integer programming that enables the refinement of geometric
min-max relations given by linear programming Strong Duality into combinatorial
min-max theorems. The definition of total dual integrality (TDI) revolves
around the existence of optimal dual solutions that are integral, and thus
naturally applies to a host of combinatorial optimization problems that are
cast as integer programs whose LP relaxations have the TDIness property.
However, when combinatorial problems are formulated using more general convex
relaxations, such as semidefinite programs (SDPs), it is not at all clear what
an appropriate notion of integrality in the dual program is, thus inhibiting
the generalization of the theory to more general forms of structured convex
optimization. (In fact, we argue that the rank-one constraint usually added to
SDP relaxations is not adequate in the dual SDP.)
  In this paper, we propose a notion of total dual integrality for SDPs that
generalizes the notion for LPs, by relying on an "integrality constraint" for
SDPs that is primal-dual symmetric. A key ingredient for the theory is a
generalization to compact convex sets of a result of Hoffman for polytopes,
fundamental for generalizing the polyhedral notion of total dual integrality
introduced by Edmonds and Giles. We study the corresponding theory applied to
SDP formulations for stable sets in graphs using the Lov\'asz theta function
and show that total dual integrality in this case corresponds to the underlying
graph being perfect. We also relate dual integrality of an SDP formulation for
the maximum cut problem to bipartite graphs. Total dual integrality for
extended formulations naturally comes into play in this context.

34
The categories of this paper are: chem-ph
13
The categories of this paper are: quant-ph
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
35
The categories of this paper are: mtrl-th
1
The categories of this paper are: cs
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
32
The categories of this paper are: atom-ph
23
The categories of this paper are: solv-int
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
7
The categories of this paper are: hep-th
30
The categories of this paper are: q-alg
14
The categories of this paper are: math-ph