An Improved Lower Bound for the Multimedian Location Problem

摘要: We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs interact. This problem, multimedian location is known to be NP-hard. give integer programming formulation this and show its linear relaxation provides lower bound superior provided by previously published formulation. also report results computational testing both formulations.