외부 열린강의
Improved Constant-Approximation for Maximum Lifetime Target Coverage
- 담당교수
- Ding-Zhu Du
- 강의수
- 1
- 수강
- 1124
- 제작연도
- NCS분류
- 공학>컴퓨터ㆍ통신>정보통신공학
- 강의설명
- 배터리 제한이 있는 많은 센서 노드들이 특정 지역에 배치되어 있을 때 목표지역을 센서들로 가능한 오랫동안 커버하기 위해 우리는 어떻게 센서들의 작동/미작동 스케줄을 계획할 수 있는지에 관한 문제는 Maximum Lifetime Coverage Problem으로 잘 알려져 있음. 이 문제를 polynomial time 안에 풀 수 있는 constant-approximation 알고리즘 설계는 오랫동안 open problem으로 남겨져 있었는데 본 특강에서는 partition과 shifting기법을 이용해 그보다 더 성능이 좋은 3.63-approximation 알고리즘을 만들 수 있는 아이디어를 소개함.
