An O(nm) algorithm for a special case of the multimedian location problem on a tree

Dilip Chhajed, Timothy J. Lowe

Research output: Contribution to journalArticlepeer-review

Abstract

The multimedian location problem on a connected network G is concerned with locating m new facilities on the network. The network G has one existing facility (customer) at each of the n nodes of G. The objective is to locate the new facilities so as to minimize total cost, which is the sum of a) weighted distances between pairs of new and existing facilities and b) weighted distances between certain pairs of new facilities. We show that this problem can be solved in O(nm) when G is a tree and the set of pairs of new facilities which interact has special structure.

Original languageEnglish (US)
Pages (from-to)222-230
Number of pages9
JournalEuropean Journal of Operational Research
Volume63
Issue number2
DOIs
StatePublished - Dec 10 1992

Keywords

  • Facilities planning
  • combinatorial analysis
  • graphs
  • location analysis

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'An O(nm) algorithm for a special case of the multimedian location problem on a tree'. Together they form a unique fingerprint.

Cite this