Laszlo Liptak

Lift-and-project ranks and antiblocker duality

  • Laszlo Liptak
  • Levent Tunçel
    • Categories Combinatorial Optimization Tags , , , , ,

    Recently, Aguilera et al.\ exposed a beautiful relationship between antiblocker duality and the lift-and-project operator proposed by Balas et al. We present a very short proof of their result that the \BCC-rank of the clique polytope is invariant under complementation. The proof of Aguilera et al. relies on their main technical result, which describes a … Read more

    The stable set problem and the lift-and-project ranks of graphs

  • Laszlo Liptak
  • Levent Tunçel
    • Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , , ,

    We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\’asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures’ performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations … Read more