Facility location with hierarchical facility costs

Abstract

We introduce a facility location problem with submodular facility cost functions, and give an O (log n ) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give a (4.237 + ϵ)-approximation algorithm using local search. The hierarchical facility costs model multilevel service installation. Shmoys et al. [2004] gave a constant factor approximation algorithm for a two-level version of the problem. Here we consider a multilevel problem, and give a constant factor approximation algorithm, independent of the number of levels, for the case of identical costs on all facilities.

Document Details

Document Type
Pub Defense Publication
Publication Date
Mar 01, 2010
Source ID
10.1145/1721837.1721853

Entities

People

  • Zoya Svitkina
  • Éva Tardos

Organizations

  • Cornell University
  • National Science Foundation
  • Office of Naval Research
  • University of Alberta

Tags

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Medical or Health Care Field.
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.