설비위치문제

위치분석이라고도 하는 FLP(Facilitary Location Problem)의 연구는 주택 주변에 위험 물질을 배치하지 않는 등의 요소와 경쟁업체의 설비 등을 고려하면서 운송비를 최소화하기 위한 시설의 최적 배치와 관련된 운영 연구와 연산 기하학의 한 분야다. 이 기법은 군집 분석에도 적용된다.

최소설비위치

단순한 설비 위치 문제는 단일 설비를 배치해야 하는 웨버 문제인데, 유일한 최적화 기준은 주어진 점 현장으로부터 거리의 가중 합계를 최소화하는 것이다. 이 분야에서 고려되는 보다 복잡한 문제에는 다중 설비의 배치, 설비의 위치에 대한 제약 및 보다 복잡한 최적화 기준이 포함된다.

기본 제형에서 시설위치 문제는 시설을 개방할 수 있는 잠재적 시설부지 L 집합과 서비스해야 하는 수요지점 D 집합으로 구성된다. 목표는 개방할 시설의 하위 집합 F를 선택하고, 각 수요 지점에서 가장 가까운 시설까지의 거리의 합과 시설의 개방 비용의 합을 최소화하는 것이다.

일반 그래프의 설비 위치 문제는 (예를 들어) 세트 커버 문제에서 (예를 들어) 감소를 통해 최적으로 해결하기 어려운 NP이다. 많은 근사 알고리즘이 설비 위치 문제와 그 많은 변형에 대해 개발되었다.

클라이언트와 현장 사이의 거리 집합에 대한 가정 없이(특히, 삼각형 불평등을 만족한다고 가정하지 않고), 이 문제는 비금속 설비 위치로 알려져 있으며, 인자 O(log n) 내에서 근사치를 구할 수 있다.^[1] 이 인자는 세트 커버 문제로 인한 근사치 보존을 통해 단단하다.

고객과 사이트 사이의 거리가 리디렉션되지 않고 삼각 불평등을 충족한다고 가정할 경우, 우리는 미터법 시설 위치(MFL) 문제에 대해 이야기하고 있다. MFL은 여전히 NP 강도로 1.463보다 나은 요인 내에서 근사치하기가 어렵다.^[2] 현재 가장 잘 알려진 근사 알고리즘은 근사비 1.488을 달성한다.^[3]

미니맥스 설비위치

미니맥스 시설 위치 문제는 현장까지의 최대 거리를 최소화하는 위치를 찾는데, 여기서 한 지점에서 현장까지의 거리가 지점에서 가장 가까운 지점까지의 거리다. 형식적 정의는 다음과 같다: P ⊂ point ℝ^d ⊂ 점 집합^d S ⊂ ⊂, S = k를 찾아 max_{p ∈ P}(d_{q ∈ S}(p(p, q) )를 최소화한다.

k = 1에 대한 유클리드 메트릭의 경우 가장 작은 주변 영역 문제 또는 1-중심 문제로 알려져 있다. 그것의 연구는 적어도 1860년까지 추적했다. 자세한 것은 가장 작은 동그라미와 경계 구를 보라.

NP 경도

k-center 문제의 정확한 해결은 NP가 어렵다는 것이 입증되었다.^[4] ^[5] ^[6] 에러가 작을 때 문제의 근사치 역시 NP가 딱딱하다는 것이 밝혀졌다. 근사 알고리즘의 오차 수준은 근사치 인수로 측정되며, 근사치와 최적값 사이의 비율로 정의된다. 근사계수가 1.822(^[7]치수 = 2) 또는 2(치수 > 2) 미만일 때 k-center 문제 근사치가 NP 하드라는 것이 입증되었다.^[6]

알고리즘

정확한 해결사

이 문제에 대한 정확한 해결책을 도출하기 위한 알고리즘이 존재한다. 정확한 용해제 1개는 $n^{O({\sqrt {k}})}$ $n^{O({\sqrt {k}})}$ O ( $){\$ n $^{O({\sqrt{k}}}}}}}}}}}}}}}}}})$ 로 실행된다 $n^{O({\sqrt {k}})}$ ^[8]^[9]

1 + ε 근사치

1 + ε 근사치는 근사계수가 1 + ε 이하인 용액을 구하는 것이다. 이 근사치는 ε이 임의적이기 때문에 NP hard이다. 코어셋 개념에 기반한 하나의 접근방식은 실행 복잡성이 O $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ k $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ / $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ 2 $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ ) ${\displaystyle O(2^{O(k\log$ k $/\varepsilon ^{2}dn)}$ 의 실행 복잡성으로 제안되며 $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ ^[10] 대안으로 코어셋에 기반한 다른 알고리즘도 이용할 수 있다. $O(k^{n})$ ( $O(k^{n})$ $O(k^{n})$ ) ${\displaystyle O(k^{n}})$ 로 실행된다 $O(k^{n})$ ^[11] 저자는 러닝타임이 최악의 경우보다 훨씬 적기 때문에 k가 작을 때(예: k < 5) 일부 문제를 해결할 수 있다고 주장한다.

가장 멀리 떨어진 지점 클러스터링

문제의 경도에는 정확한 해법이나 정확한 근사치를 구하는 것이 비현실적이다. 대신, 큰 k 사례에는 요인 = 2의 근사치가 널리 사용된다. 근사치는 가장 먼 지점 군집화(FPC) 알고리즘 또는 가장 먼 첫 번째 횡단이라고 한다.^[6] 알고리즘은 매우 간단하다: 세트에서 중앙으로 원하는 점을 선택하고, 나머지 중앙에서 다른 중앙으로 설정된 가장 먼 지점을 검색하며, k 센터가 발견될 때까지 이 과정을 반복한다.

이 알고리즘은 선형 시간으로 실행되는 것을 쉽게 알 수 있다. 요인이 2 미만인 근사치는 NP 하드인 것으로 입증되므로 FPC는 찾을 수 있는 가장 좋은 근사치로 간주되었다.

실행 성과에 따라, 시간 복잡성은 나중에 박스 분해 기법으로 O(n log k)로 개선된다.^[7]

최대설비위치

최대 시설 위치 또는 불쾌한 시설 위치 문제는 현장까지의 최소 거리를 최대화하는 위치를 찾는다. 유클리드 지표의 경우 가장 큰 빈 구문제로 알려져 있다. 평면 케이스(빈 원 문제 중 가장 큰 것)는 최적의 시간 n(n log n)에 해결할 수 있다.^[12]^[13]

정수 프로그래밍 공식

시설 위치 문제는 정수 프로그램으로 해결되는 경우가 많다. 이러한 맥락에서 시설 위치 문제는 종종 다음과 같이 제기된다: $n$ $n$ 개의 $n$ 시설과 $m$ $m$ 개의 $m$ 고객이 있다고 가정하자. 최소 비용으로 일부 고정 수요를 충족하기 위해 $n$ ${\displaystyle$ n $}개$ 의 시설 $n$ 중 (1)을 열고 (2) m $m$ 고객을 $m$ 공급하기 위해 사용할 시설(개방) 우리는 다음과 같은 표기법을 도입한다: $f_{i}$ f {\ $displaystyle$ $f_{i}$ f_{ $i}$ 는 i $i=1,\dots ,n$ $i=1,\dots ,n$ $i=1,\dots ,n$ $i=1,\dots ,n$ ${\displaystyle i=1,\dots,$ $c_{ij}$ $}$ 에 대한 $시설$ i ${\$ 는 시설 $i$ $i$ 에서 고객로 제품을 $i$ 배송하는 (고정액정) 비용을 $f_{i}$ $c_{ij}$ 나타낸다 $i=1,\dots ,n$ $\displaystyle j}$ for $i=1,\dots ,n$ and $j=1,\dots ,m$ . Let $d_{j}$ denote the demand of customer $j$ for $j=1,\dots ,m$ . Further suppose that each facility has a maximum output. Let $u_{i}$ i ${\$ $u_$ ${i}$ 는 $시설$ i ${\displaystyle$ i $i$ $u_{i}$ let u ${\$ 이(가) $시설$ i ${\displaystystyle i}$ 의 용량을 나타낼 $u_{i}$ 수 있는 최대 제품 양을 나타낸다 $u_{i}$ $i$ 이 조의 나머지 부분은 다음과^[14] 같다.

콘덴서식위치

초기 공식에서 $i=1,\dots ,n$ = 1 $i=1,\dots ,n$ , $i=1,\dots ,n$ … $i=1,\dots ,n$ , $i=1,\dots ,n$ $i=1,\dots ,n$ 에 $x_{i}$ 대한 이진 변수 $x_{i}$ i $x_{i}$ $i$ 을(를) 도입하십시오 $i$ $i=1,\dots ,n$ 여기서 $x_{i}=1$ $x_{i}=1$ $x_{i}=1$ = $x_{i}=1$ ${\displaystyle x_{i}=1}=$ $x_{i}=0$ }, $x_{i}=0$ $x_{i}=0$ = 0 ${\displaystyle x_{i}=0$ }=0 $}$ $d_{j}$ 로 $j=1,\dots ,m$ 설비 $i$ $i=1,\dots ,n$ = $i=1,\dots ,n$ , $i=1,\dots ,n$ … $i=1,\dots ,n$ , n ${\displaystyle i=1,\dots,$ $j=1,\dots ,m$ $}$ 및 $j=1,\dots ,m$ = 1 $j=1,\dots ,m$ , $j=1,\dots ,m$ ${\$ $j=1$ $,\dots$ $,m}$ 에 $y_{{ij}}$ 대한 $d_{j}$ $y_{ij}$ y $y_{ij}$ j $i$ 을(를) 도입하십시오 $i$ 이른바 콘덴서식 설비 위치 문제는 다음에 의해 주어진다.

{\displaystyle {\rl}\min &\displaystyle \sum \sum _{i=1}^{i=1}c_{ij}d_{jjj}++\{i=1}^{n_{n_{ix_{i}\t.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}

$두$ 번째 제한조건 집합은 x $x_{i}=0$ = 0 ${\displaystyle x_{i}=0$ 즉 facility $i$ ${\displaystyle$ $i}$ 이 $y_{ij}=0$ (가) 열려 있지 $i$ 않으면 $y_{ij}=0$ = $y_{ij}=0$ ${\displaystyle$ $y_{ij}=0$ $j$ 즉, facility $i$ ${\displaystytyle i}$ 에서 어떤 고객에 대한 요구도 채울 수 없음을 보장한다는 점에 유의하십시오 $i$

무절제한 시설위치

위의 정전식 설비 위치 문제의 일반적인 경우는 $u_{i}=+\infty$ = + $∞$ {\ $displaystyle u_{i}=+\inflt }$ $i=1,\dots ,n$ i $i=1,\dots ,n$ = $i=1,\dots ,n$ , $i=1,\dots ,n$ $i=1,\dots ,n$ ${\displaysty i=1$ ,\ $dots,n}.$ 이 경우 가장 가까운 개방형 설비에서 $고객$ $j$ ${\displaysty$ j $}$ 의 모든 요구를 만족시키는 것이 항상 최적이다. 이 때문에 위의 연속 $y_{ij}$ 변수 $y_{ij}$ $y_{ij}$ ${\$ 을(를) $z_{ij}$ 변수 $z_{ij}$ i $z_{ij}$ j {\ $displaystyle z_{$ ij $}}$ 로 교체할 수 있으며 $z_{ij}$ $z_{ij}=1$ 서 $고객$ $z_{ij}=1$ ${\$ $displaystyle j}$ 이 $z_{ij}=1$ $j$ $z_{ij}=1$ 가) $시설$ i ${\displaystystyle$ i $}$ 및 $z_{ij}=0$ = $.$ 그렇지 $z_{ij}=0$ 않으면 $디스플레이 스타일 z_$ {ij $}=0}.$ 무절제한 시설 위치 문제는 다음에 의해 주어진다.

{\displaystyle {\rl}\min &\displaystyle \sum \sum _{i=1}c_{ij}d_{j}z_{ij}++\{i=1}^{i=1}f_{ix_{i}\cext.t.t.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}

여기서 $M$ $M$ 은 $M$ (는) 적절한 크기로 선택된 상수다. $M$ $M$ 의 선택은 계산 결과에 영향을 미칠 수 있다 $M$ . 이 경우 최선의 선택은 다음과 $M=m$ : take $M=m$ = m ${\displaystyle M=m$ 그런 다음 $x_{i}=1$ $x_{i}=1$ = $x_{i}=1$ $x_{i}=1$ 인 경우 $z_{ij}$ $z_{ij}$ $z_{ij}$ ${\$ 의 어떤 선택이든 두 번째 제한조건을 만족시킬 것이다 $z_{ij}$ $x_{i}=1$

계획되지 않은 설비 위치 문제에 대한 또 다른 공식 가능성은 용량 제약 조건(빅 $M$ ${\디스플레이$ 스타일 $M}$ 제약 $M$ 조건)을 세분화하는 것이다. 즉, 제약 조건을 대체한다.

\sum \{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{{}모든 }i=1,\dots,n

제약을 받고

z_{ij}\leqslant x_{i}{\text{{}}{\text{{}}모든 }i=1,\reason,n{\text{} 및 }j=1,\reason,m

실제로, 이 새로운 공식은 첫 번째 공식보다 더 촘촘한 선형 프로그래밍 완화를 가지고 있다는 점에서 훨씬 더 좋은 성능을 발휘한다.^[14] 새로운 제약 조건을 종합하면 원래 빅

M

M

제약

M

조건이 발생한다는 점에 유의하십시오. 축전된 경우, 이러한 제형은 동등하지 않다. 무삭제 시설위치 문제에 대한 자세한 내용은 "구체적 위치이론" 제3장에서 확인할 수 있다.^[15]

적용들

헬스케어

의료에서, 잘못된 시설 위치 결정은 단순한 비용 및 서비스 측정 기준을 넘어 지역사회에 심각한 영향을 미친다. 예를 들어 접근하기 어려운 의료 시설은 질병성 및 사망률 증가와 관련될 가능성이 높다. 이러한 관점에서 보건의료 시설 위치 모델링은 다른 영역의 유사한 모델링보다 더 중요하다.^[16]

고형 폐기물 관리

도시의 고형 폐기물 관리는 폐기물 생산 증가와 폐기물 관리와 관련된 높은 비용 때문에 개발도상국들에게 여전히 과제로 남아 있다. 시설 입지 문제의 제형과 정확한 해결을 통해 쓰레기 처리를 위한 매립지의 위치를 최적화할 수 있다.^[17]

클러스터링

클러스터 분석 문제의 특정 부분집합은 설비 위치 문제로 볼 수 있다. 중심 기반 클러스터링 문제에서 목표는 $n$ $n$ 데이터 $n$ 점(공통 메트릭 공간의 요소)을 동일한 색상의 점들이 서로 근접하도록 동등성 클래스(흔히 색상이라고 함)^[18]로 분할하는 것이다(동일하게, 다른 색상의 점들이 서로 멀리 떨어져 있도록).

중심 기반 클러스터링 문제를 시설 위치 문제로 보는 방법("변환" 또는 "감소")을 보려면 전자의 각 데이터 지점을 후자의 요구 지점으로 보십시오. 클러스터링할 데이터가 메트릭 $공간$ M ${\displaystyle$ $M}$ 의 요소라고 가정하십시오( $M$ 예: $p$ 된 p ${\$ $displaystyle p}$ - 차원 $p$ 유클리드 공간인 $p$ 고정 $p$ p ${\$ $displaystyle p}$ 우리가 건설하고 있는 설비 위치 문제에서, 우리는 이 미터법 공간 $M$ 의 $어느$ 지점에든 설비를 배치할 수 있도록 허용한다 $M$ 이것은 $L$ 되는 설비 위치 L ${\\displaystyle L}$ 의 집합을 정의한다 $L$ 우리는 loca 사이의 쌍방향 거리로 비용 $c_{\ell ,d}$ $c_{\ell ,d}$ $c_{\ell ,d}$ , $c_{\ell ,d}$ ${\$ 을 정의한다.tion-demand point pair(예: 미터법 k-center 참조) 중심 기반 클러스터링 문제에서는 데이터를 각각 중심이 있는 $k$ $k$ 동등성 $k$ 클래스(즉, 색상)로 분할한다. 구성된 시설 위치 문제에 대한 해결책이 이러한 파티션을 어떻게 달성하는지 봅시다. 실현 가능한 해결책은 $k$ $k$ 위치의 $L'\subseteq L$ $k$ 비어 있지 않은 부분 $L'\subseteq L$ L $L'\subseteq L$ $L'\subseteq L$ {\ $displaystyle$ L $'\subseteq L}$ 이다. 시설 위치 문제의 이러한 위치는 중심 기반 클러스터링 문제에 있는 $k$ 의 k $k$ 중심으로 $k$ 구성된다. Now, assign each demand point $d$ to the location $\ell ^{*}$ that minimizes its servicing-cost; that is, assign the data point $d$ to the centroid ${\displaystyle \ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\e$ $ll ,d}\}($ 임의로 동점을 끊는다. 이는 설비 위치 문제의 비용 $c_{\ell ,d}$ $c_{\ell ,d}$ , $c_{\ell ,d}$ ${\$ 이(가) 중심 기반 클러스터링 문제의 거리 함수의 이미지로 정의되는 $c_{\ell ,d}$ 경우 분할을 달성한다.

인기 있는 알고리즘 교재 알고리즘 설계는 관련 문제 설명과 근사 알고리즘을 제공한다. 저자는 중앙 선택 문제로 미터법 시설 위치 문제(즉, 중심 기반 클러스터링 문제 또는 $미터법$ k $k$ -center $k$ 문제)를 언급하여, 이에 따라 동의어 목록이 커진다.

또한 위의 설비 위치 문제에 대한 정의에서 목표 함수 $f$ $f$ 이(가) 일반적이라는 $f$ 것을 확인하십시오. $f$ $f$ 의 구체적인 선택은 설비 위치 문제의 다른 변형을 야기하며 $f$ , 따라서 중심 기반 클러스터링 문제의 다른 변형을 야기한다. 예를 들어, 각 위치로부터 할당된 각 요구 지점까지의 거리의 합계를 최소화하도록 선택할 수도 있고(베버 문제에 대해), 또는 그러한 모든 거리의 최대값을 최소화하도록 선택할 수도 있다(중앙 문제에 대해).

참고 항목

참조

^ Hochbaum, D. S. (1982). "Heuristics for the fixed cost median problem". Mathematical Programming. 22: 148–162. doi:10.1007/BF01581035.
^ Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006/jagm.1998.0993.
^ Li, S. (2011). "A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem". Automata, Languages and Programming. LNCS. Vol. 6756. pp. 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.
^ Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), "Optimal packing and covering in the plane are NP-complete", Information Processing Letters, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.
^ Megiddo, Nimrod; Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane" (PDF), Operations Research Letters, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.
^ ^a ^b ^c Gonzalez, Teofilo (1985), "Clustering to minimize the maximum intercluster distance" (PDF), Theoretical Computer Science, 38: 293–306, doi:10.1016/0304-3975(85)90224-5, archived from the original (PDF) on 2013-01-24.
^ ^a ^b Feder, Tomás; Greene, Daniel (1988), "Optimal algorithms for approximate clustering", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing: 434–444, doi:10.1145/62212.62255, ISBN 0897912640
^ HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), "The slab dividing approach to solve the Euclidean p-center problem", Algorithmica, 9 (1): 1–22, doi:10.1007/BF01185335
^ HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), "The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time", Algorithmica, 9 (4): 398–423, doi:10.1007/bf01228511
^ Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing: 250–257, doi:10.1145/509907.509947, ISBN 1581134959
^ Kumar, Pankaj; Kumar, Piyush (2010), "Almost optimal solutions to k-clustering problems" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142/S0218195910003372
^ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. ISBN 978-0-387-96131-6. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989., 페이지 256
^ G. T. Toussaint, "위치 제약이 있는 가장 큰 빈 원 계산", 국제 컴퓨터 및 정보 과학 저널, 제12권, 제5권, 1983년 10월, 페이지 347–358.
^ ^a ^b Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Integer Programming SpringerLink. Graduate Texts in Mathematics. Vol. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.
^ Discrete location theory. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.{{cite book}}: CS1 maint : 기타(링크)
^ Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "A Survey of Healthcare Facility Location". Computers & Operations Research. 79: 223–263. doi:10.1016/j.cor.2016.05.018.
^ Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). "Optimization in waste landfilling partitioning in Paraná State, Brazil". Journal of Cleaner Production. 283. doi:10.1016/j.jclepro.2020.125353.
^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). The elements of statistical learning (Second ed.). Springer.
^ Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson.

외부 링크

위치 분석에 관한 EWGLA EURO 작업 그룹.
시설 입지와 관련된 전문 사회인 위치 분석에 관한 정보를 제공한다.
Trevor Hale이 수집한 3400개 이상의 기사가 수록된 시설 위치에 대한 참고 문헌 목록.
위치 알고리즘 라이브러리
웹 기반 시설 위치 유틸리티(단일 시설)
설비 위치 문제 해결을 위한 MATLAB 기반 툴인 Facility Location Optimizer.

[1] Hochbaum, D. S. (1982). "Heuristics for the fixed cost median problem". Mathematical Programming. 22: 148–162. doi:10.1007/BF01581035.

[2] Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006/jagm.1998.0993.

[3] Li, S. (2011). "A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem". Automata, Languages and Programming. LNCS. Vol. 6756. pp. 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.

[4] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), "Optimal packing and covering in the plane are NP-complete", Information Processing Letters, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.

[5] Megiddo, Nimrod; Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane" (PDF), Operations Research Letters, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.

[Gonzalez1985-6] Gonzalez, Teofilo (1985), "Clustering to minimize the maximum intercluster distance" (PDF), Theoretical Computer Science, 38: 293–306, doi:10.1016/0304-3975(85)90224-5, archived from the original (PDF) on 2013-01-24.

[Feder1988-7] Feder, Tomás; Greene, Daniel (1988), "Optimal algorithms for approximate clustering", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing: 434–444, doi:10.1145/62212.62255, ISBN 0897912640

[8] HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), "The slab dividing approach to solve the Euclidean p-center problem", Algorithmica, 9 (1): 1–22, doi:10.1007/BF01185335

[9] HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), "The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time", Algorithmica, 9 (4): 398–423, doi:10.1007/bf01228511

[10] Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing: 250–257, doi:10.1145/509907.509947, ISBN 1581134959

[11] Kumar, Pankaj; Kumar, Piyush (2010), "Almost optimal solutions to k-clustering problems" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142/S0218195910003372

[ps256-12] Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. ISBN 978-0-387-96131-6. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989., 페이지 256

[13] G. T. Toussaint, "위치 제약이 있는 가장 큰 빈 원 계산", 국제 컴퓨터 및 정보 과학 저널, 제12권, 제5권, 1983년 10월, 페이지 347–358.

[:0-14] Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Integer Programming SpringerLink. Graduate Texts in Mathematics. Vol. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.

[15] Discrete location theory. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.{{cite book}}: CS1 maint : 기타(링크)

[Ahmadi-16] Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "A Survey of Healthcare Facility Location". Computers & Operations Research. 79: 223–263. doi:10.1016/j.cor.2016.05.018.

[17] Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). "Optimization in waste landfilling partitioning in Paraná State, Brazil". Journal of Cleaner Production. 283. doi:10.1016/j.jclepro.2020.125353.

[18] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). The elements of statistical learning (Second ed.). Springer.

[19] Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Search