Viviani's theorem

2013-09-04T20:49:44Z

24.188.20.165: Undid revision 563532881 by 14.98.186.79 (talk)

{{Refimprove|date=May 2009}}
The '''facility location problem''', also known as '''location analysis''' or '''k center problem''', is a branch of [[operations research]] and [[computational geometry]] concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing and competitors' facilities. The techniques also apply to [[cluster analysis]].

==Minisum facility location==

A simple facility location problem is the [[Weber problem]], in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted sum of distances from a given set of point sites. More complex problems considered in this discipline include the placement of multiple facilities, constraints on the locations of facilities, and more complex optimization criteria.

In a basic formulation, the facility location problem consists of a set of potential facility sites ''L'' where a facility can be opened, and a set of demand points ''D'' that must be serviced. The goal is to pick a subset ''F'' of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities.

The facility location problem on general graphs is [[NP-hard]] to solve optimally, by reduction from (for example) the [[set cover problem]]. A number of approximation algorithms have been developed for the facility location problem and many of its variants.

Without assumptions on the set of distances between clients and sites (in particular, without assuming that the distances satisfy the [[triangle inequality]]), the problem is known as '''non-metric facility location''' and can be approximated to within a factor O(log(n)).<ref>{{cite doi|10.1007/BF01581035}}</ref> This factor is tight, via an [[approximation-preserving reduction]] from the set cover problem.

If we assume distances between clients and sites are undirected and satisfy the triangle inequality, we are talking about a '''Metric Facility Location''' problem (MFL). The MFL is still NP-hard and hard to approximate within factor better than 1.46. The currently best known approximation algorithm achieves approximation ratio of 1.488.<ref>{{cite doi|10.1007/978-3-642-22012-8_5}}</ref>

==Minimax facility location==
The '''minimax facility location''' problem seeks a location which minimizes the maximum distance to the sites, where the distance from one point to the sites is the distance from the point to its nearest site. A formal definition is as follows:
Given a point set '''''P''''' ⊂ ℝd, find a point set '''''S''''' ⊂ ℝd, |'''''S'''''|=k, so that max'''q'''∈'''''S'''''(min'''p'''∈'''''P'''''(d('''p''','''q''')) ) is minimized.

In the case of the Euclidean metric for k=1, it is known as the [[smallest enclosing sphere]] problem or [[1-center problem]]. Its study traced at least to the year of 1860. see [[smallest enclosing circle]] and [[bounding sphere]] for more details.

===NP Hardness===
It's proved that exact solution of k center problem is NP hard.<ref>{{citation
| last1 = Fowler| first1 = R.J.
| last2 = Paterson | first2 =M.S.
| last3 = Tanimoto | first3 = S.L.
| journal = Information processing letters
| pages = 133–137
| title = Optimal packing and covering in the plane are NP-complete
| volume = 12
| year = 1981}}.</ref>
<ref>{{citation
| last1 = Megiddo| first1 = Nimrod| authorlink = Nimrod Megiddo
| last2 = Tamir| first2 =Arie
| journal = Operations Research Letters
| pages = 194–197
| title = [http://theory.stanford.edu/~megiddo/pdf/complexity%20of%20locating%20linear%20facilities.pdf On the complexity of locating linear facilities in the plane]
| volume = 1
| issue = 5
| year = 1982}}.</ref>
<ref name="Gonzalez1985">{{citation
| last = Gonzalez| first = Teofilo
| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
| pages = 293–306
| title = [http://www.cs.ucsb.edu/~TEO/papers/Ktmm.pdf Clustering to minimize the maximum intercluster distance]
| volume = 38
| year = 1985}}.</ref>
Approximation to the problem was found to be also NP hard when the error is small. The error level in [[Approximation algorithm]] is measured as approximation factor, which is defined as the ratio between the approximation and the optimum. It's proved that the k center problem approximation is NP hard when approximation factor is less than 1.822 (dimension = 2)<ref name="Feder1988">{{citation
| last1 = Feder | first1 = Tomás
| last2 = Greene| first2 =Daniel
| journal = Proceedings of the twentieth annual ACM symposium on Theory of computing
| pages = 434–444
| title = [http://theory.stanford.edu/~tomas/clustering.ps Optimal algorithms for approximate clustering]
| year = 1988}}</ref> or 2 (dimension >2).<ref name = Gonzalez1985/>

===Algorithms===
'''Exact solver'''

There exist algorithms to produce exact solutions to this problem. One exact solver runs in time <math>O(n^{\sqrt{k}})</math> <ref>{{citation
| last1=HWang |first1= R. Z.
| first2=R. C. T. | last2= Lee
| first3=R. C. | last3= Chang
| title = [http://link.springer.com/article/10.1007%2FBF01185335?LI=true# The slab dividing approach to solve the Euclidean p-center problem]
| journal = Algorithmica
| year = 1993
| volume = 9
| issue = 1
| pages = 1–22}}</ref>
.<ref>{{citation
| last1=HWang |first1= R. Z.
| first2=R. C. | last2= Chang
| first3=R. C. T. | last3= Lee
| title = [http://link.springer.com/article/10.1007%2FBF01228511?LI=true# The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time]
| journal = Algorithmica
| year = 1993
| volume = 9
| issue = 4
| pages = 398–423}}</ref>

'''1 + ε Approximation'''

1+ε approximation is to find an solution with approximation factor no greater than 1+ε. This approximation is NP hard as ε is arbitrary. One approach based on core-set concept is proposed with execution complexity of <math>O(2^{O(\frac{k \log{k}}{\epsilon^{2}}))}dn)</math><ref>{{citation
|first1=Mihai |last1= Bādoiu
|first2=Sariel |last2=Har-Peled
|first3=Piotr |last3= Indyk
|title= [http://www.cs.duke.edu/courses/spring07/cps296.2/papers/badoiu02approximate.pdf Approximate clustering via core-sets]
|journal = Proceedings of the thirty-fourth annual ACM symposium on Theory of computing
|pages = 250–257
|year = 2002
}}</ref>
. As an alternative, another algorithm also based on core-set is available. It runs in <math>O(k^n)</math>>.<ref>{{citation
|first1=Pankaj |last1= Kumar
|first2=Piyush |last2= Kumar
|title= [http://compgeom.com/~piyush/papers/kcenter.pdf Almost optimal solutions to k-clustering problems]
|journal=International Journal of Computational Geometry & Applications
|volume= 20
|issue= 04
|year= 2010
}}</ref> The author claims that the running time is much less than the worst case and thus it's possible to solve some problems when k is small (say k<5).

'''Farthest Point Clustering'''

For the hardness of the problem, it's impractical to get an exact solution or precise approximation. Instead, an approximation with factor=2 is widely used for large k cases. The approximation is referred the Farthest Point Clustering (FPC) algorithm.<ref name=Gonzalez1985/> The algorithm is quite simple: pick any point from the set as one center; search for the farthest point from remaining set as another center; repeat the process until k centers are found.

It's easy to see that this algorithm runs in linear time. As approximation with factor less than 2 is proved to be NP hard, FPC was regarded as the best approximation one can find.

As per the performance of execution, the time complexity is later improved to <math>O(n \log{k})</math> with box decomposition technique.<ref name=Feder1988/>

==Maxmin facility location==
The '''maxmin facility location''' or '''obnoxious facility location''' problem seeks a location which maximizes the minimum distance to the sites. In the case of the Euclidean metric, it is known as the [[largest empty sphere]] problem. The planar case ([[largest empty circle]] problem) may be solved in [[time complexity|optimal time]] <math>\Theta(n\, \log\, n)\,.</math> <ref name=ps256>{{cite book
|author = [[Franco P. Preparata]] and [[Michael Ian Shamos]] | title = Computational Geometry - An Introduction | publisher = Springer-Verlag| year = 1985 | id = 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6}}, [http://books.google.com/books?id=gFtvRdUY09UC&pg=PA256&lpg=PA256&dq=%22minimax+facilities+location%22&source=bl&ots=dNgqxVw_fA&sig=l1wPWBd1PrIEMnVIMJbAb-a_OAg&hl=en&ei=tIo5S8zeOZGCswP6mJXQBA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAgQ6AEwAA#v=onepage&q=%22minimax%20facilities%20location%22&f=false p. 256]</ref><ref>G. T. Toussaint, "Computing largest empty circles with location constraints," ''International Journal of Computer and Information Sciences'', vol. 12, No. 5, October, 1983, pp. 347-358.</ref>

==See also==
*[[Graph center]]
*[[Quadratic assignment problem]]

==References==
{{reflist}}

== External links ==
*[[INFORMS]] [http://location.section.informs.org/ section on location analysis], a professional society concerned with facility location.
*[http://gator.dt.uh.edu/~halet/ Bibliography on facility location] collected by Trevor Hale, containing over 3400 articles.
*[http://www.mathematik.uni-kl.de/~lola/ Library of location algorithms]
*[http://sporkforge.com/opt/facility_locate.php Web-based facility location utility (single facility)]

{{DEFAULTSORT:Facility Location}}
[[Category:Operations research]]

formulasearchengine - User contributions [en]

Viviani's theorem