Analysis of Lagrangian lower bounds for a graph partitioning problem

Analysis of Lagrangian lower bounds for a graph partitioning problem

0.00 Avg rating0 Votes
Article ID: iaor20011258
Country: United States
Volume: 47
Issue: 5
Start Page Number: 785
End Page Number: 788
Publication Date: Sep 1999
Journal: Operations Research
Authors: ,
Keywords: networks
Abstract:

Recently, Ahmadi and Tang demonstrated how various manufacturing problems can be modeled and solved as graph partitioning problems. They use Lagrangian relaxation of two different mixed integer programming formulations to obtain both heuristic solutions and lower bounds on optimal solution values. In this note, we point to certain inconsistencies in the reported results. Among other things, we show analytically that the first bound proposed is trivial (i.e., it can never have a value greater than zero) while the second is also trivial for certain sparse graphs. We also present limited empirical results on the behavior of this second bound as a function of graph density.

Reviews

Required fields are marked *. Your email address will not be published.