Analysis of Lagrangian lower bounds for a graph partitioning problem
成果类型：
Article
署名作者：
Adil, GK; Ghosh, JB
署名单位：
University of Manitoba; Ihsan Dogramaci Bilkent University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.5.785
发表日期：
1999
页码：
785-788
关键词：
摘要：
Recently, Ahmadi and Tang (1991) 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.