- 거리의 합이 최소가 되는${lambda}$ 이산 2-중심 문제
- ㆍ 저자명
- 신찬수,Shin. Chan-Su
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2002년|29권 6호|pp.340-345 (6 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
본 논문에서는 기관위치설정 문제 중에서, 이차원 평면에 주어진 n개의 점들로 구성된 집합 P에 대한 이산 2-중심 문제를 다룬다. P의 있는 서로 다른 두 점을 중심으로 선택하는 데, P의 다른 점들은 두 중심 중에서 가까운 중심가지의 거리의 최대값과 두 중심 사이의 거리의 합이 최소가 되도록 선택하는 것이 목적이다. 본 논문에서는 Ο(n$^2$logn) 시간에 이산 2-중심을 구하는 알고리즘을 제시한다.
In this paper, we deal with the following facility location problem. Given a set P of n points in the plane, find two (discrete) centers p and q in P that minimize the sum of there distance plus the distance of any other point to the closer center. In this paper, we propose an Ο(n$^2$1ogn)-time algorithm to compute the two centers.