절단 된 격차를 최소화하기위한 일정

Question

단위 길이의 단일 작업, $ n $ 슬롯 및 $ b $ 단위. 슬롯 $ T $ 에서 작업이 예약 된 경우 $ C (t) $ 단위를 사용합니다 예산 $ B $ . $ x $ 연속 슬롯의 기간 동안 일시적으로 일정이없는 경우 $ \ lfloor x / 2의 벌금 \ rfloor $ 이 발생합니다. 목표는 벌칙의 합을 최소화하기 위해 일을 예약하는 것입니다.

예를 들어, 작업이 슬롯 3, 슬롯 3, 슬롯 6 및 슬롯 $ n= 12 $ 의 경우,="수학 용기"> $ 12 $ , 페널티의 합계는 $ \ lfloor 1/2 \ rfloor + \ lfloor 2/2 \ rfloor + \ lfloor 5 / 2 \ rfloor= 0 + 1 + 2= 3 $ .

이 문제는 np-hard입니까?

나는 그것에 탈출구 문제를 줄이려고 노력하고 있습니다. 직각의 값을 페널티스로 변환하는 것은 $ T $ 에서 작업이 예약되면 페널티가 초기화됩니다.

Answer 1

문제는 다항식 시간이 솔루브 가능합니다. 가장자리 케이스를 피하기 위해 $ 0 $ 및 $ c (0)에서 일시적으로 예약해야한다고 생각하는 것이 좋습니다. )= 0 $ .

$ opt [T, P] $ 첫 번째 $ T $ 대부분의 $ p $ 및 작업이 예약되어야하는 추가 제약 조건을 가진 슬롯 시간 $ T $ .

$ p (t ', t)=big \ lfloor \ frac {t-t'-1} {2} \ big rfloor $ 작업이 때때로 $ T '$ 및 $ t> t'$ 을 예약하면 발생하는 페널티 언제든지간에 예약되지 않습니다.

그런 다음 $ opt [0, p]= 0 $ 및 $ t> 0 $ : $$ 옵트 [T, P]= C (T) + \ min _ {\ subscack {T '= 0, \ dots, t-1 \\ p (t', t) \ le p}} opt \ left [t ', p - p (t ', t) \ right] $$

시간 $ T $ 의 최소 달성 가능한 패널티 $ T $ 은 다음과 같습니다. $$ \ mU (t)=min \ {p \ in \ {1, \ dots, \ lfloor t / 2 \ rfloor \} \ mid opt [t, p] \ le b \} $$

및 귀하의 문제에 대한 최소 달성 가능한 벌금은 다음과 같습니다. $$ \ min_ {t= 0, \ dots, n} \ left \ {\ mu (t) + p (t, n + 1) \ right \}. $$

대부분의 $ n \ cdot (p (0, n) +1)= O (n ^ 2) $ 값 $ OPT [P, T] $