Skip to main content
5 of 5
deleted 26 characters in body

One general class of functions I have just found, perhaps a hint as to an even more general class, where the sort-and-scan approach works, (sorting pairs $(a,b)$ decreasing by $a/b$) is $F(x) = x$, and $G(x) = x^\gamma$ for any power $0 < \gamma < 1$ (subsuming one of the given examples when $\gamma = 1/2$). Hopefully someone else can come up with an even more general class with a proof though.

Update: Requested proof (and note the claimed class of functions has been reduced to just a parametrized family because I realized a small gap in the original proof that just assumed $G'(x)/G(x) \leq \beta/x$ for some $\beta < 1$).

For $G = x^\gamma$, $0 < \gamma < 1$, and $F(x) = x$, let $A,B$ be positive, and consider a pair of terms $(a_i,b_i)$. Take the derivative of $F(A + \alpha a_i) / G(B + \alpha b_i)$ with respect to $\alpha$, this is $a_i/G(B + \alpha b_i) - b_i(A + \alpha a_i)G'(B + \alpha b_i)/(G(B + \alpha b_i))^2$, and since $b_i, G$ are positive we can multiply by $G$ and divide by $b_i$ to get the following term which has the same sign as the derivative: $H(\alpha) = a_i/b_i - \gamma (A + \alpha a_i)/(B + \alpha b_i)$, where recall $\gamma < 1$. $H(\alpha)$ is the expression we will work with to establish two facts that complete the proof. Suppose that we have a non-empty solution of pairs giving $A = \sum_{i \in I} a_i$ and $B = \sum_{i \in I} b_i$, and we have a pair $(a_i,b_i)$ not in the solution. Firstly, if $a_i/b_i \geq A/B$, then clearly $H(\alpha) > 0$ for all $\alpha > 0$, so adding $(a_i,b_i)$ to the solution will increase the objective. Alternatively, suppose $a_i/b_i < A/B$ and adding $(a_i,b_i)$ to the solution increases the objective, and suppose there is another pair $(a_j,b_j)$ ($j \neq i$) not included in the solution which satisfies $a_j/b_j \geq a_i/b_i$. Then if we add both pairs to the solution, the objective is greater than or equal to $F(A + \alpha_0 a_i) / G(B + \alpha_0 b_i)$ for $\alpha_0 = (b_i + b_j)/b_i > 1$. Note $H(\alpha)$ is increasing for $\alpha > 0$ because $A/B > a_i/b_i$. Furthermore $H(\alpha)$ must be positive for some positive $\alpha < 1$ because $F(A + a_i)/G(B + b_i) > F(A)/G(B)$ by assumption. Thus the derivative is positive for all $\alpha \in [1, \alpha_0]$, so additionally adding $(a_j,b_j)$ to the solution further increases the objective. These two facts prove that the optimal solution must have the property that when you sort pairs decreasing according to $a/b$, the optimal solution must be the first $k$ pairs for some $k$.