The multi-facility median problem with Pos/Neg weights on general graphs

Joerg Kalcsics*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this paper we discuss the multi-facility location problem on networks with positive and negative weights. As the finite dominating set for the single facility problem does not carry over to the multi-facility problem, we derive a new finite dominating set. To solve the problem, we present a straight-forward algorithm. Moreover, for the problem with just two new facilities, we show how to obtain a more efficient solution procedure by using planar arrangements. We present computational results to underline the efficiency of the improved algorithm and to test some approximations which are based on a reduced candidate set.

Original languageEnglish
Pages (from-to)674-682
Number of pages9
JournalComputers and Operations Research
Issue number3
Publication statusPublished - Mar 2011

Keywords / Materials (for Non-textual outputs)

  • Finite dominating sets
  • Multi-facility location problems
  • Networks
  • Planar arrangements


Dive into the research topics of 'The multi-facility median problem with Pos/Neg weights on general graphs'. Together they form a unique fingerprint.

Cite this