Back to search

University of Waterloo

Improved approximation guarantees for lower-bounded facility location problem

Abstract

dc:description.abstract

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ahmadian, Sara

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/5513

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ahmadian, Sara. Improved approximation guarantees for lower-bounded facility location problem. University of Waterloo, 2010. http://hdl.handle.net/10012/5513