Antoniadis 등이 ICLR 2025에서 NP-hard 선택 문제를 근사하기 위한 예측 기반 프레임워크를 제안했어요. 이 프레임워크는 이론적 하한에 가깝고 일반화 성능이 뛰어나요.
연구진은 Antoniadis 등의 연구에서 제기된 질문에 답하기 위해 스케줄링 문제에 이 접근법을 확장했어요.
학습 기반 알고리즘을 활용해 관련 없는 기계에서의 Makespan 최소화 문제를 해결했으며, 정확한 예측 시 (1+ε) 근사, 오차가 증가하면 최대 2배 근사 성능을 보여줘요.