An approximation algorithm for the maximization version of the two level uncapacitated facility location problem

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

A polynomial time approximation algorithm for the shifted two level MAX uncapacitated facility location problem (UFLP) problem was described. The problem was based on the technique of independently randomized rounding. The facilities in each level were opened and assigned each demand point to a path along open facilities such that the total profit was maximized when facilities were located on k levels. It was found that even if the facilities were opened independently, the events corresponding to paths being opened became dependent.

Original languageBritish English
Pages (from-to)155-161
Number of pages7
JournalOperations Research Letters
Volume29
Issue number4
DOIs
StatePublished - Nov 2001

Keywords

  • Approximation algorithms
  • Facility location
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'An approximation algorithm for the maximization version of the two level uncapacitated facility location problem'. Together they form a unique fingerprint.

Cite this