Lesson 22: Network Algorithms and Approximations by Mohammad Hajiaghayi: Iterative Rounding Method 1
Mohammad Hajiaghayi · 69:02 · Watch on YouTube
이 강의는 Kamal Jain의 1998년 작업에서 시작된 근사 알고리즘을 위한 LP 기반 방법인 반복적 반올림(iterative rounding)과 반복적 이완(iterative relaxation)을 소개합니다. 핵심 주장은 극단점(기본 실행 가능) LP 해가 적은 수의 타이트한 제약을 가지므로, 최소한 하나의 변수는 정수이거나 크다(예: 최소 ½)는 것입니다. 그 변수를 반올림하거...