On the commutativity of antiblocker diagrams under lift-and-project operators (Q2500533): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Q867923 / rank
Normal rank
 
Property / author
 
Property / author: Q1941536 / rank
Normal rank
 
Property / author
 
Property / author: Mariana S. Escalante / rank
 
Normal rank
Property / author
 
Property / author: Graciela L. Nasini / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.dam.2006.03.026 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2015198705 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lift and project relaxations for the matching and related polytopes / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Generalization of the Perfect Graph Theorem Under the Disjunctive Index / rank
 
Normal rank
Property / cites work
 
Property / cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On certain polytopes associated with graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum matching and a polyhedron with 0,1-vertices / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5708498 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index” / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric algorithms and combinatorial optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5476491 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The stable set problem and the lift-and-project ranks of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Cones of Matrices and Set-Functions and 0–1 Optimization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Applying Lehman's theorems to packing problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Representation of the Matching Polytope Via Semidefinite Liftings / rank
 
Normal rank

Latest revision as of 19:21, 24 June 2024

scientific article
Language Label Description Also known as
English
On the commutativity of antiblocker diagrams under lift-and-project operators
scientific article

    Statements

    On the commutativity of antiblocker diagrams under lift-and-project operators (English)
    0 references
    0 references
    0 references
    0 references
    17 August 2006
    0 references
    The behaviour of the disjunctive operator in the context of the ``antiblocker duality diagram'' associated with the stable set polytope, \(\text{QSTAB}(G)\), of a graph and its complement has been studied by \textit{N. Aguilera, M. Escalante} and \textit{G. Nasini} [Math. Oper. Res. 27, 460--469 (2002; Zbl 1083.05505)]. The main consequence of this work is a generalization of the perfect graph theorem under disjunctive rank. The behaviour of the lift-and-project operators \(N_0, N\) and \(N_{+}\) has been studied by Lipták and Tunçel. They found an example of graph for which the diagram does not commute in one iteration of the \(N_0, N\) and \(N_{+}\) operator. In the present paper the authors give, for any number of iterations, explicit proofs of noncommutativity of the \(N_0, N\) and \(N_{+}\) diagram. In the particular case of the \(N_0\) and \(N\) operator, they found exact bounds for the ranks of the complements of line graphs (of complete graphs).
    0 references
    0 references
    stable set problem
    0 references
    antiblocker duality
    0 references
    disjunctive rank
    0 references
    0 references