Unrelated Machines Makespan 스케줄링을 위한 학습 증강 근사 기법
요약
본 논문은 Antoniadis 등의 프레임워크를 확장하여, 비관련 기계(unrelated machines)에서의 makespan 최소화 스케줄링 문제에 대한 학습 증강 근사 알고리즘을 개발했습니다. 이 방법은 작업 할당 예측값을 활용해 다항 시간 내 $(1+\varepsilon)$-근사를 달성하며, 오차 증가 시 최악 사례 2-근사로 수렴함을 보였습니다.
핵심 포인트
- Antoniadis 등의 연구를 스케줄링 문제에 확장 적용함.
- 비관련 기계 makespan 최소화 문제를 다룸 ($R||C_{\max}$).
- 예측값을 사용해 $(1+\varepsilon)$-근사를 달성하는 알고리즘 개발.
최근 Antoniadis 등(ICLR 2025)은 예측값을 통합하여 NP-난해 선택 문제(selection problems)를 근사하는 프레임워크를 제안했습니다. 이 접근 방식은 단순함에도 불구하고 이론적 하한선에 매우 가깝게 일치하며, 그 일반화 가능성이 매우 흥미롭습니다. 우리는 Antoniadis 등의 연구에서 제기된 열린 질문, 즉 선택 문제의 범주를 벗어난 다른 중요한 문제들(예: 스케줄링)로 이 접근 방식을 확장하는 것에 대해 다룹니다. 우리는 비관련 기계(unrelated machines)에서의 makespan 최소화 문제($R||C_{\max}$)에 대한 학습 증강 알고리즘을 개발했습니다. 무거운 작업 할당에 대한 예측값을 사용함으로써, 정확한 예측값의 경우 다항 시간 내 $(1+\varepsilon)$-근사를 달성하며, 오차가 증가함에 따라 부드럽게 최악 사례 2-근사로 저하됩니다. 마지막으로 본 연구에서는 저희 방법론에 대한 경험적 분석을 제시합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기