Facility location with red-blue demands

Sonika Arora*, Neelima Gupta, Samir Khuller, Yogish Sabharwal, Swati Singhal

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Facility location and data placement problems have been widely studied. Consider the following problem. We are given a set of facilities F and a set of clients D in a metric space. There are two types of objects. A client may have demand for each of the object types. A facility can be opened for one or both types depending on its storage capacity; there are no facility opening costs. The goal is to determine the facilities to open for each type while respecting their storage capacity constraints and assign every demand to a facility open for its type. We present a 4-approximation LP-rounding based algorithm for this problem.

Original languageEnglish (US)
Pages (from-to)462-465
Number of pages4
JournalOperations Research Letters
Volume42
Issue number6
DOIs
StatePublished - Jan 1 2014

Keywords

  • Approximation algorithms
  • Facility location
  • LP-rounding

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Facility location with red-blue demands'. Together they form a unique fingerprint.

Cite this