# AO 6
<!-- [AO 5](https://hackmd.io/@Anadi/BJlKYRdvi) -->
[AO 5](https://hackmd.io/@Anadi/BJlKYRdvi/edit)


### a)

#### Co najwyżej $2 - \frac 1m$

Nie wprost. Załóżmy że dla pewnego wejścia $a_n$ OPT osiąga obciążenie $l$, oraz że ALG przekracza obciążenie $2l - \frac lm$ w pewnym kroku $i$.

Powiedzmy że ALG umieszcza zadanie $a_i$ na maszynie $j$.

Niech $v_j$ oznacza obciążenie na maszynie $j$ przed krokiem $i$. Wiemy, że $v_j + a_i > 2l - \frac lm$. $a_i$ jest na pewno równe co najwyżej $l$.

Wiemy, że sumaryczne obciążenie wszystkich maszyn może wynieść najwyżej $ml$. Zatem, na innych niż $j$ maszynach jest co najwyżej $$ml - (2l - \frac lm) = (m - 1)l - (l - \frac lm) = (m-1)l - \frac{(m-1)l}m$$czyli istnieje maszyna, na której obciążenie wynosi co najwyżej
$$\frac {(m - 1)l - \frac {(m-1)l}m}{m-1} = l - \frac l{m}$$ Stąd istnieje maszyna, na której zadanie $a_i$ zmieściłoby się w limicie, a z założenia nie wprost ALG umieścił je na takiej maszynie, że limit został przekroczony. Sprzeczność.

#### Co najmiej $2 - \frac 1m$

Wystarczy dać algorytmowi $m(m-1)$ zadań o rozmiarze $\frac lm$, a następnie jedno o rozmiarze $l$.

OPT ułoży początkowe krótsze zadania na $m-1$ maszynach, a następnie umieści ostatnie zadanie na jeszcze nieobciążonej maszynie, osiągając obciążenie $l$.

ALG ułoży zadania początkowe równomiernie na wszystkich maszynach, a następnie położy ostatnie zadanie gdziekolwiek. Stąd osiągnie obciążenie $(m-1)\frac lm + l = 2l - \frac{1}{m}$.

### b)

Rozważmy rozkład jednostajny na dwóch następujących ciągach: $a=(\frac{1}{2},\frac{1}{2})$ oraz $b=(\frac{1}{2},\frac{1}{2},1)$.

Jak widać, istnieją 2 sensowne algorytmy - taki, który układa pierwsze 2 mniejsze elemeny na 2 różnych maszynach, oraz taki, który ustawia je na jednej i zostawia miejsce na drugiej.

* $E(ALG1) = \frac 12 \frac12 + \frac 12 \frac32 = 1$
* $E(ALG2) = \frac 12 1 + \frac 12 1 = 1$

$E(OPT) = \frac 12 \frac12 + \frac 12 1 = \frac 34$.

Zatem z zasady minmaxowej mamy ograniczenie dolne: $\frac{1}{\frac 34} = \frac{4}{3}$.


Rozwiązanie będzie przebiegało zgodnie ze schematem.
Z wykładu wiemy, że $R = \max(d_1, \sup_i \frac{s_{i+1}}{d_i})$.

i) Z warunku powyżej wynika $\frac{s_{j+2}}{d_{j+1}} \leq R$, czyli $s_{j+2} \leq R \cdot (s_{j+1} - s_j)$.

ii) $(b_{j+1} - b_j) \cdot b_j \leq -b_j^2 + Rb_j - R$, równoważnie $b_{j+1} \cdot b_j \leq R(b_j - 1)$.
Wstawiając z definicji: $\frac{s_{j+2}}{s_j} \leq R\frac{s_{j+1} - s_j}{s_j}$, co jest prawdą na mocy i).

iii) Jest to funkcja kwadratowa zmiennej $b_j$, z współczynnikiem $a < 0$, wystarczy zatem, że nie ma pierwiastków. $\Delta = R^2 - 4(-1)(-R) = R(R-4)$. Dla $0 < R < 4$ mamy $\Delta < 0$, zatem OK.

iv) $b_j$ jest zbieżny, bo jest malejący i dodatni. Lewa strona zbiega do $0$, a prawa strona zbiega do $-b^2 + Rb - R$. Dla $0 < R < 4$ wiemy, że prawa strona jest ujemna, zatem sprzeczność. Stąd $R \geq 4$.


Rozważmy algorytm, który skonstruuje nam rozwiązanie optymalne dla kolejnych potęg dwójki -- $1, 2, 4, \ldots, 2^{\lceil \log M \rceil}$. Tutaj, $OPT(k)$ dla $k > |M|$ oznacza po prostu $OPT(|M|)$.
Może on nie istnieć w $P$, ale nie przejmujemy się tym zgodnie ze wskazówką. Oznaczmy przez $X_1, X_2, X_4, \ldots$ zbiory, które wybierzemy w optymalnym rozwiązaniu. Rozważmy algorytm, który skonstruuje zbiory $F_1, F_2, \ldots, F_M$ w następujący sposób:
$$
F_i = \bigcup_{j = 1}^{\lceil \log i \rceil} X_{2^j}
$$

Łatwo zauważyć, że $OPT(s) \geq OPT(s + 1)$, bo możemy wziąć te same fabryki co w mniejszym rozwiązaniu i dowolną inną, a koszt nam nie wzrośnie. Stąd z pewnością:
$$
COST(F_i) \leq OPT(2^{\lceil \log i \rceil}) \leq OPT(i)
$$

Z drugiej strony, $|F_i| \leq \sum_{j = 1}^{\lceil \log i \rceil} 2^j < 2 \cdot 2^{\lceil \log i \rceil} < 4 \cdot i$. Jako, że w oczywisty sposób zbiory $F_i$ są rosnące, to kończy to dowód na konstrukcję wyżej wymienionych ciągów.