KSC 2019
Current Result Document : 5 / 5
| 한글제목(Korean Title) |
홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 알고리즘의 효율적이고 강건한 구현 |
| 영문제목(English Title) |
Efficient and Robust Implementation of the Algorithms for Parity-Constrained k-Center and Facility Location |
| 저자(Author) |
김강산
안형찬
Kangsan Kim
Hyung-Chan An
|
| 원문수록처(Citation) |
VOL 46 NO. 02 PP. 1224 ~ 1226 (2019. 12) |
한글내용
(Korean Abstract) |
본 논문에서는 홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 정확한 알고리즘과 근사 알고리즘을 개선하기 위한 휴리스틱을 제안하고, 이들을 실험적으로 평가한다. 이들 두 문제는 이론적인 면에서뿐만 아니라 실용적으로도 중요한 문제로서, 상수 인자 근사 알고리즘이 알려져 있다. 그러나 실제로 이들 문제에 대한 최적해 혹은 근사해를 찾는, 실용적으로 적합한 구현을 얻기 위한 연구는 거의 이루어지지 못하였다. 본 논문에서는 이를 보완하기 위해 알고리즘의 수행 속도, 해의 질, 수치 에러를 개선하는 휴리스틱을 설계하고 실제 데이터셋에서의 성능을 측정한다. 이외에도, 기존에 알려진 상수 인자 근사 알고리즘이 정확한 알고리즘에 비해 성능에 있어 어떠한 차이를 보이는지 평가한다.
|
영문내용
(English Abstract) |
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
