Problem: Given $c \in \mathbb { R } _ { + } ^ { n } , a \in \mathbb { R } _ { + } ^ { n }$ and $\gamma \in \mathbb { R } _ { + } ,$ design an algorithm which, in $O ( n \log n )$ operations, computes the optimal solution $x ^ { * }$ to the following linear program :
$$\begin{array} { c l } { \max } & { c ^ { T } x } \\ { \text { s.t. } } & { a ^ { T } x \leq \gamma } \\ { } & { 0 \leq x _ { i } \leq 1 , \quad \forall i \in [ n ] } \end{array}$$
You may assume that a set of $n$ real numbers can be sorted in time $O ( n \log n )$ and that each arithmetic operation takes constant time.
Thanks to @lonzaleggiera on my previous post I managed to write an algorithm in $O ( n \log n )$ time that compute an optimal solution to my LP. I am now trying to prove optimality. Here you can find his answer:
You sort the $c _ { i } / a _ { i }$ from highest to lowest: $c _ { i _ { 1 } } / a _ { i _ { 1 } } , c _ { i _ { 2 } } / a _ { i _ { 2 } } , \ldots , c _ { i _ { n } } / a _ { i _ { n } } ,$ and find the largest value of $k$ for which $\sum _ { j = 1 } ^ { k } a _ { i _ { j } } \leq \gamma ,$ then set $x _ { i _ { j } } = 1$ for $j = 1,2 , \ldots , k ,$ and $$x _ { i _ { k + 1 } } = \left( \gamma - \sum _ { j = 1 } ^ { k } a _ { i _ { j } } x _ { i _ { j } } \right) / a _ { i _ { k + 1 } }$$
My attempt: Suppose for a contradiction $\exists y \in \mathbb { R }^ { n }$ such that $c^T x < c^T y$, with $x$ the output of our algorithm.
$\Rightarrow \exists j_0 \in \text{{$1,...,n$}}$ s.t $c_{i_{j_0}}x_{i_{j_0}} < c_{i_{j_0}}y_{i_{j_0}} $
$\Rightarrow x_{i_{j_0}} < y_{i_{j_0}} $ since $c_{i_{j_0}} \neq 0$
We can now study 3 cases :
If $j_0 \in \text{{$1,...,k$}}$: then $x_{j_0} = 1 < y_{j_0}$ since $0\leq y_i \leq 1$ by our constraints. Contradiction
If $j_0 = k +1$: then $x_{j_0} = x_{k+1} < y_{k+1}$
$\Rightarrow \frac{\gamma - s}{a_{i_{k+1}}} < y_{k+1}$
$\Rightarrow \gamma < s + a_{i_{k+1}}y_{k+1} = \sum_{j=1}^{k+1} a_{i_j}y_j \leq \sum_{j=1}^{n} a_{i_j}y_j$
$\Rightarrow \gamma < a^T t$ Contradiction
If $j_0 \in \text{{$k+2,...,n$}}$ and here I'm lost.
What would be your strategy to solve this last case? The issue is that I don't have much information on my optimal solution $y$ and I don't know where the contradiction would rise off.
I would prove this by demonstrating a solution to the dual linear program that has the same objective value as the primal solution you obtained. Let me know if you need more of a hint.