maximum independent set

A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

  • Miguel F. Anjos
  • Youssouf Emine
  • Andrea Lodi
  • Zhao Sun
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Network Optimization Tags , , ,

    In this note, we consider several polynomial optimization formulations of the max- imum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior. … Read more

    Fast Local Search for the Maximum Independent Set Problem

  • Diogo V. Andrade
  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Meta Heuristics, Stochastic Approaches Tags , , ,

    Given a graph G = (V,E), the independent set problem is that of finding a maximum-cardinality subset S of V such that no two vertices in S are adjacent. We introduce two fast local search routines for this problem. The first can determine in linear time whether a maximal solution can be improved by replacing … Read more