Approximation algorithms for facility location problems

A.F. Bumb

Research output: ThesisPhD Thesis - Research UT, graduation UT

1081 Downloads (Pure)

Abstract

Facility location problems are among the most well-studied problems in optimization literature. The simplest variant is the uncapacitated facility location problem, which we denoted by the UFLP. In the UFLP, we are given a set of possible facility locations and a set of clients. The problem seeks to find a set of locations to build/open facilities such that the sum of the cost of building/opening the facilities and the cost of serving each client from exactly one open facility is minimized. This problem is NP−hard. Therefore, many heuristics for finding good approximate solutions were developed. In this thesis we design approximation algorithms for several variants of the UFLP.
Original languageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Woeginger, Gerhard, Supervisor
  • Faigle, U., Supervisor
Award date4 Oct 2002
Place of PublicationEnschede
Publisher
Print ISBNs9036517877
Publication statusPublished - 4 Oct 2002

Keywords

  • METIS-207710
  • IR-38644

Fingerprint Dive into the research topics of 'Approximation algorithms for facility location problems'. Together they form a unique fingerprint.

Cite this