The search for optimal Lagrange multipliers

摘要

Lagrangean constramt relaxation methods are a widely used approximation technique for NP-hard discrete optimization problems. The computational complexity of the Lagrangean relaxation technique is examined in this paper. It is shown that the optimization