diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 4 |
1 files changed, 2 insertions, 2 deletions
@@ -176,7 +176,7 @@ includefoot=true,top=19mm,nohead,footskip=12mm,bottom=6mm]{geometry} This is also easily disproved as a bad idea. To find a counter example, just take two long jobs that do not conflict, then put a shorter job that conflicts with both. \subsubsection{Sort jobs by smallest number of job interval conflicts} This one is also not optimal. It requires a slightly more complex counter example.\\ - Note that this option is also dependent on the order we pick. The counter example chosen illustrates this. + Note that this option is also dependent on the order we pick. Why is that? Because {\bf we are ordering by number of conflicts in $\mathcal{J}$.} When we pop an element from $\mathcal{J}$, we remove this element from $\mathcal{J}$, so in reality the number of conflicts is not static, but dynamic. Try it for yourself, and then see how the second example is more resilient against ordering. \subsubsection{Sort jobs by finish time} This option will be guaranteed to produce an optimal outcome.\\ \subsection{Proving that sorting by finish time is optimal} @@ -187,7 +187,7 @@ includefoot=true,top=19mm,nohead,footskip=12mm,bottom=6mm]{geometry} Running Time:\\ If we pick a competent sorting algorithm, we can finish the sort in $\mathcal{O}(n\log n) + \mathcal{O}(n) = \mathcal{O}(n\log n)$} \subsubsection{Promising Proof} - \proofbox{lemma}{bruh} + \proofbox{lemma}{bruh}{nada} We say ``promising'', because here, we want to prove that every partial answer is a subset of an optimal answer. First we will need the promising set lemma, which goes as follows:\\ Lemma: Promising set $\forall\text{ iter } t\exists \text{ opti set } A^*_t \st A_T \subseteq A^*_t$\\ In regular English, this means for each iteration $t$, it's partial solution is a subset of an optimal solution.\\ |