Facility location problem

In a Facility Location Problem (FL ) is an optimization problem in which it comes from a set of locations choose a subset as a supply locations that they are optimally placed under the given conditions. The exact finding such subsets is considered algorithmically difficult and is generally NP-hard.

Introduction

Applications of facility location are very diverse. It may be intended for health care optimal locations of hospitals, for companies represents, for example, the question of location of factories, but also in the course of the ever continuing expansion of the Internet, the question arises of smart positioning of servers.

Generally it can be formulated a FL as follows: For given amounts of consumers and service providers and given cost is from the set of vendors a subset are found, so that each consumer is served by exactly one supplier, thereby minimizing costs. A further variant of FL is produced when it is required that each load is supplied by at least one provider.

The costs can be broken down from the pairs present connection costs between consumers and providers, and the cost of opening and / or operation of a provider.

Example

Modeling

A FL is usually modeled as a complete bipartite graph, where the Bipartion from the union of two disjoint sets of providers ( facilities) and consumer ( customer) is created. In addition, two positive pictures ( connection charges ) and ( Eröffnungs-/Betriebskosten ) are defined. Applies to the cost function an extended triangle inequality, we use the term metric Facility Location Problem:

Wanted is a subset and an assignment that:

Minimized.

Solubility

Since this is an NP - hard problem in Facility Location, approximation algorithms are used to solve. In contrast to the metric facility location problem that can be approximated with a constant quality, the general facility location problem can (in which the triangle inequality does not have to apply ) are not better than approximated. Below are some approximation algorithms are given which approximate the metric facility location problem with constant quality:

Jain - Vazirani algorithm

Kamal Jain and Vijay Vazirani presented in 2001 an algorithm, based on a primal- dual variant of a linear program. They found evidence that the result is a 3- approximation, ie more than three times worse than the optimum. The running time of the algorithm is, with.

Mahdian, Ye- Zhang algorithm

Mohammad Mahdian, Ye and Yinyu Yiawei Zhang published in 2002 a variant of a greedy algorithm that approximates a solution of a problem with the FL- kindness. The much better factor by which the maximum solution differs from the optimum must, however, with a higher running time ( with ) to be paid as of the Jain - Vazirani algorithm.