About the greedy solution for a specific linear-fractional programming problem

Question

Let $a_i>0, b_i>0, \forall i $.

The optimizing problem is $$\max_{x_i}(\frac{\sum_{i=1}^{n}x_i a_i b_i}{\sum_{i=1}^{n}x_i b_i})$$ with constrains: \begin{align} x_i \in \{0,1\}\\ \sum_{i=1}^{n}x_i b_i\geq B \end{align}

A naive idea is to sort $\{(a_i, b_i)\}$ according to $a_i$ decs, then sum $b_i$ until the constrain is satisfied. This is call the greedy solution.

The question is how bad can it be comparing to the best solution. And under what condition it is the best solution.

Answer 1

Here is some my own thinking.

Firstly, it's easy to find a case that greedy solution is not the best. For example, $\{(a_i, b_i)\} = \{(100, 1), (10,100), (1,1)\}$ and $B=2$. The greedy solution is $\{1,2\}$ while the best is $\{1,3\}$.

Secondly, when bound $B$ is coincidentally reached for the greedy solution, then it's the best solution. Formally:

Proposition A:

Assumping $\{(a_i, b_i)\}$ is sorted, namely $a_1\geq a_2\geq\dots\geq a_n$ and when $B=\sum_1^k b_i$ for some $k$, then the greedy solution is the best solution.

Proof: Let $\{x_i\}$ be any feasible solution. Denote \begin{align} & p_0:= \frac{\sum_{i=1}^{k}x_i a_i b_i}{\sum_{i=1}^{k}x_i b_i}, q_0 := \sum_{i=1}^{k}x_i b_i \\ & p_1:= \frac{\sum_{i=k+1}^{n}x_i a_i b_i}{\sum_{i=k+1}^{n}x_i b_i}, q_1 := \sum_{i=k+1}^{n}x_i b_i \\ & p_2:= \frac{\sum_{i=1}^{k}(1-x_i) a_i b_i}{\sum_{i=1}^{k}(1-x_i) b_i}, q_2 := \sum_{i=1}^{k}(1-x_i) b_i \end{align} Then since it's feasible, $q_0+q_1 \geq B=q_0+q_2$, so we have $q_1\geq q_2$. On the other hand, easy to see: $p1\leq a_k\leq p2$ and $p1\leq a_k\leq p0$. Therefore \begin{align} & \frac{\sum_{i=1}^{n}x_i a_i b_i}{\sum_{i=1}^{n}x_i b_i}=\frac{\sum_{i=1}^{k}x_i a_i b_i + \sum_{i=k+1}^{n}x_i a_i b_i}{\sum_{i=1}^{k}x_i b_i + \sum_{i=k+1}^{n}x_i b_i} \\ \\ =& \frac{p_0 q_0+p_1 q_1}{q_0+q_1}\leq \frac{p_0 q_0+p_2 q_2}{q_0+q_2} \qquad(*)\\ \\ =&\frac{\sum_{i=1}^{k}x_i a_i b_i + \sum_{i=1}^{k}(1-x_i) a_i b_i}{\sum_{i=1}^{k}x_i b_i + \sum_{i=1}^{k}(1-x_i) b_i} = \frac{\sum_{i=1}^{k}a_i b_i}{\sum_{i=1}^{k}b_i} \end{align}

Thus the greedy solution is the best solution. The inequality $(*)$ is proved in the following Lemma.

Lemma: If $p1\leq p2$ and $p1\leq p0$ and $q_1 \geq q_2$ then $$\frac{p_0 q_0+p_1 q_1}{q_0+q_1}\leq \frac{p_0 q_0+p_2 q_2}{q_0+q_2}$$ proof: since $p_1\leq p_0$ and $q_1 \geq q_2$, we have \begin{align} & (q_1-q_2)p_1 \leq (q_1-q_2)p_0 \implies \\ & (q_0 q_2)p_0+(q_0 q_1)p_1 \leq (q_0 q_1)p_0+(q_0 q_2)p_1 \implies \\ & (p_0 q_0+p_1 q_1)(q_0+q_2)=(q_0^2+q_0 q_2)p_0+(q_0 q_1+q_1 q_2)p_1 \\ & \leq (q_0^2+q_0 q_1)p_0+(q_0 q_2+q_1 q_2)p_1 = (p_0 q_0+p_1 q_2)(q_0+q_1) \implies \\ &\frac{p_0 q_0+p_1 q_1}{q_0+q_1}\leq \frac{p_0 q_0+p_1 q_2}{q_0+q_2} \end{align} and since $p_1\leq p_2$ $$ \frac{p_0 q_0+p_1 q_2}{q_0+q_2} \leq \frac{p_0 q_0+p_2 q_2}{q_0+q_2}$$ End of proof. $\square$

By the Proposition A, we can get an error estimation for greedy solution. Denote $B_k = \sum_1^k b_i$ and $V(B)$ and $G(B)$ the value of best solution and greedy solution with bound B respectively. For $B_k < B \leq B_{k+1}$, by the definition of "best solution" we have $$G(B_{k+1})=G(B)\leq V(B) \leq G(B_{k})$$ which implies $$0 \leq V(B)-G(B) \leq G(B_{k}) - G(B_{k+1})$$ In many practical applications, this upper bound is small enough.