초록 ▼

□ 연구개요
산업 전반에 걸쳐 빈발하는 최적화 문제들은 흔히 NP-난해하므로, 이러한 문제들에 접하여는 다소 해의 질을 희생하더라도 빠른 시간 내에 최적에 가까운 해를 찾아내는 근사 알고리즘을 적용할 필요가 있다. 근사 알고리즘을 설계하기 위해 다양한 알고리즘 기법이 개발되어 왔으나, 그 중에서도 특히 선형계획법에 기반한 방법이 가장 성공적이었다. 본 연구에서는 선형계획법에 기초한 근사 알고리즘 설계 방법론을 강화하고자, 아래와 같은 세 가지의 상호보완적이며 단계적인 목표 하에 연구를 수행하였다. 가. 널리 알려진 난제 해결.

□ 연구개요
산업 전반에 걸쳐 빈발하는 최적화 문제들은 흔히 NP-난해하므로, 이러한 문제들에 접하여는 다소 해의 질을 희생하더라도 빠른 시간 내에 최적에 가까운 해를 찾아내는 근사 알고리즘을 적용할 필요가 있다. 근사 알고리즘을 설계하기 위해 다양한 알고리즘 기법이 개발되어 왔으나, 그 중에서도 특히 선형계획법에 기반한 방법이 가장 성공적이었다. 본 연구에서는 선형계획법에 기초한 근사 알고리즘 설계 방법론을 강화하고자, 아래와 같은 세 가지의 상호보완적이며 단계적인 목표 하에 연구를 수행하였다. 가. 널리 알려진 난제 해결. 나. 선형 계획법에 기초한 새로운 기법 개발.
다. 근사 알고리즘의 계산적 평가.

□ 연구 목표대비 연구결과
목표 가. 널리 알려진 난제 해결
-홀짝성 제약이 있는 설비 위치 선정 문제에 대한 연구를 통해, 향후 새로운 연구분야를 개척해 나갈 선도적 연구를 수행
-설비 위치 선정 및 클러스터링 문제들의 근사 알고리즘에 대한 survey를 통해, 국제적인 연구자들의 해당 분야에 대한 관심을 제고함
-s-t경로 외판원 문제는 해외 연구자 그룹에서 결과를 선점하였으나, 이 연구를 통해 얻어진 기법을 다른 연구 문제에 활용

목표 나. 선형 계획법에 기초한 새로운 기법 개발
-온라인 이분 매칭에 대한 연구를 수행함. 기존에 널리 연구되고 관심받은 바 있는 이 문제에 대해 보다 일반화되고 현실적인 모델을 제안하는 연구로, 잠재력 있음.
-랜덤성을 공유하는 LP-라운딩 근사 알고리즘을 통해 새로운 알고리즘 기법을 제시함.

목표 다. 근사 알고리즘의 계산적 평가
-용량 제약이 있는 설비 위치 선정 문제에 대한 선형계획법 완화의 정수 격차를 실험적으로 측정함. 본 연구를 통해 향후 계산적 연구의 기틀을 마련함.

□ 연구개발결과의 중요성
조합론적 최적화 문제에 대한 근사 알고리즘의 연구는 태생적으로 다양한 응용 가능성을 내포하여 중요한 파급효과를 가진다. 뿐만 아니라, 본 연구를 통해 얻어진 알고리즘 기법은 이론 컴퓨터과학 연구에도 응용될 수 있다.

특히, 홀짝성 제약이 있는 설비 위치 선정 문제에 대한 연구는 향후 새로운 연구영역을 개척할 것이 기대되며, 온라인 이분 매칭 문제에 대한 연구 역시 실질적으로나 이론적으로나 큰 파급 효과를 가질 것으로 기대된다. 근사 알고리즘의 계산적 평가에 대한 연구 역시 향후 계산적 연구를 수행하는 데에 기틀을 마련한 것으로 평가되어, 본 연구 과제를 통해 수행된 개별 연구 결과 역시 명백한 중요성을 보인다.

(출처 : 연구결과 요약문 3p)

목차 Contents

• 표지 ... 1
• 연구결과 요약문 ... 3
• 목차 ... 4
• 1. 연구개발과제의 개요 ... 4
• 가. 근사 알고리즘 연구의 필요성 ... 4
• 나. 선형 계획법에 기초한 근사 알고리즘 설계 ... 5
• 다. 본 연구의 필요성 및 3대 목표 ... 6
• 2. 연구수행내용 및 연구결과 ... 7
• 가. 널리 알려진 난제 해결 (100% 달성) ... 7
• 나. 선형 계획법에 기초한 새로운 기법 개발 (100% 달성) ... 9
• 다. 근사 알고리즘의 계산적 평가 (100% 달성) ... 10
• 3. 연구개발결과의 중요성 ... 12
• 4. 참고문헌 ... 13
• 5. 연구성과 ... 14
• 대표적 연구실적 ... 16
• 끝페이지 ... 22