lagrangian relaxation

Strengthened Semidefinite Relaxations via a Second Lifting for the Max-Cut Problem

  • Miguel F. Anjos
  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    In this paper we study two strengthened semidefinite programming relaxations for the Max-Cut problem. Our results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. We prove that the first relaxation provides a strengthening of the Goemans-Williamson relaxation. The second relaxation is a further tightening of the first … Read more

    Solving Steiner tree problems in graphs with Lagrangian relaxation

  • Laura Bahiense
  • Francisco Barahona
  • Oscar Porto
    • Categories Graphs and Matroids Tags , ,

    This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due … Read more