온라인 알고리즘 (Online Algorithm)

온라인 알고리즘 (Online Algorithm)

입력이 순차적으로 주어지며 각 입력에 대해 즉시 결정을 내려야 하는 알고리즘으로, 미래 입력을 모르는 상태에서 결정하며 경쟁비(Competitive Ratio)로 성능 측정

목적: 실시간 의사결정, 미래 정보 없는 최적화, 경쟁비 분석

특징: 순차 입력, 즉시 결정, 취소 불가(대부분), 경쟁비 분석

경쟁비(Competitive Ratio)

• •온라인 비용 / 오프라인 최적 비용 (최소화 문제)
• •c-competitive: ALG(σ) ≤ c * OPT(σ) + α

대표 문제

• •페이지 교체: LRU는 k-competitive (k=캐시 크기)
• •스키 렌탈: 구매비용/렌탈비용 = B/r 날까지 렌탈 후 구매, 2-competitive
• •List Update: Move-to-Front, 2-competitive
• •k-서버 문제: k개 서버로 요청 처리, (2k-1)-competitive

Ski Rental 문제

• •렌탈: $1/일, 구매: $B
• •최적 전략: B일 동안 렌탈 후 구매 → 2-competitive

결정론적 vs 확률적

• •결정론적: 고정 전략, 더 나쁜 경쟁비
• •확률적: 무작위화로 적대적 입력 대응, 더 좋은 경쟁비

장점: 실시간 처리, 메모리 효율, 스트리밍 데이터 처리

단점: 최적해 아님, 문제별 하한 존재, 분석 어려움

적용사례: 캐시, 스케줄링, 라우팅, 주식 거래, 자원 할당

비교: 온라인(미래모름/경쟁비) vs 오프라인(전체입력/최적) vs 스트리밍(대용량/근사)

연관: 경쟁 분석, 캐시 교체, 스케줄링, 의사결정