정보과학회논문지 (Journal of KIISE)
Current Result Document : 1 / 1
| 한글제목(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 48 NO. 03 PP. 0264 ~ 0274 (2021. 03) |
한글내용
(Korean Abstract) |
본 논문에서는 홀짝성 제약이 있는 k-센터 및 설비 위치 선정 문제에 대한 정확한 알고리즘과 근사 알고리즘을 개선하기 위한 휴리스틱을 제안하고, 이들을 실험적으로 평가한다. 이들 두 문제는 이론적 인 면에서뿐만 아니라 실용적으로도 중요한 문제로서, 상수 인자 근사 알고리즘이 알려져 있다. 그러나 실제로 이들 문제에 대한 최적해 혹은 근사해를 찾는, 실용적으로 적합한 구현을 얻기 위한 연구는 거의 이루어지지 못하였다. 본 논문에서는 이를 보완하기 위해 알고리즘의 수행 속도, 해의 질, 수치 에러를 개선하는 휴리스틱을 설계하고 실제 데이터셋에서의 성능을 측정한다. 이외에도, 기존에 알려진 상수 인자 근사 알고리즘이 정확한 알고리즘에 비해 성능에 있어 어떠한 차이를 보이는지 검증한다.
|
영문내용
(English Abstract) |
In this paper, we present heuristics for improving the exact and approximation algorithms for parity-constrained k-center and facility location problems, along with their computational evaluations. For the theoretical and practical relevance of these problems, constant-factor approximation algorithms are known for both problems. Unfortunately, few studies have been conducted to obtain a practically adequate implementation of exact and/or approximation algorithms for either problem. This paper fills in this gap by devising heuristics to improve the running time, solution quality, and numerical errors of the algorithms for both problems and measuring their performance. We also evaluate the known constant-factor approximation algorithms in comparison to exact algorithms
|
| 키워드(Keyword) |
홀짝성 제약
k-센터 문제
설비 위치 선정 문제
조합 최적화 알고리즘
근사 알고리즘
휴리스틱
parity constraints
k-center problem
facility location
combinatorial optimization algorithms
approximation algorithms
heuristics
|
| 파일첨부 |
PDF 다운로드
|
