# Generalizing the linear subset scan algorithm to a wider class of objective functions, maybe by finding a paper

Given a list of pairs $(a_1,b_1),\ldots,(a_n,b_n)$, where all $a_i \geq 0$ and all $b_i > 0$, my general problem is when we can use linear subset scan (described below) to solve the optimization problem of finding the optimal combination of pairs,

$$I^* = \hbox{argmax}_I F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$$

where $F,G$ are given increasing positive functions for positive inputs.

I have found a class of functions where there is a fast solution, namely $F(x) = x + A$ and $G(x) = (x + B)^\beta$ where $A,B \geq 0$ and $0 \leq \beta \leq 1$. In this case, the optimal solution can be found by sorting all pairs $(a_i,b_i)$ in decreasing order according to $a_i/b_i$, and then trying the first $k$ pairs in sorted order for all $k$ and choosing the best solution, and this gives the optimal solution. (This is an example of linear subset scan optimization.)

Now I want to know, if there a general class of functions $F,G$, ideally defined by abstract properties, where this linear subset scan approach works, where pairs are sorted either according to $a_i/b_i$ or perhaps sorted according to $H(a_i,b_i)$ where $H$ depends on $F,G$? This could be a question where someone has a new insight and proof, or simply someone has seen something like this in the literature. At any rate, I feel like the class of $F,G$ I stated where I have a proof is perhaps not the most general possible, and I'm missing some key abstract property that makes the linear subset scan work.

• This sort things and pick the minimum somewhat looks like scheduling problems where one uses the "Weighted Shortest Processing Time first" rule... – Chao Xu Aug 9 '13 at 9:52

If I wanted to solve this problem, I wouldn't limit myself to the linear subset scan algorithm: I would consider other algorithms as well.

For instance, here is one approach that might be effective in many cases. If $\theta$ is a non-negative real number, define

$$h(\theta) = \max \left\{\sum_{i \in I} a_i : \sum_{i \in I} b_i \le \theta\right\}.$$

Note that

$$F(I^*)/G(I^*) = \max_\theta F(h(\theta))/G(\theta).$$

So, define $f:\mathbb{R}\to \mathbb{R}$ by

$$f(\theta) = F(h(\theta))/G(\theta).$$

With these definitions, our goal is to find the maximum of $f$.

Also, note that we can compute $h(\theta)$ for any given $\theta$ of our choice, using integer linear programming. (In principle, there is no guarantee that ILP will run in polynomial time, but in practice, I bet it may often be possible to compute this reasonably efficiently.) Your linear subset scan algorithm (sort the $a_i,b_i$ by decreasing value of $a_i/b_i$) is a good heuristic for efficiently computing an approximate solution to this ILP (computing a lower bound on $h(\theta)$), but as far as I can see, there is no guarantee that it will actually find the true optimum value.

This means that we can also compute $f(\theta)$ for any given $\theta$ of our choice.

So, we have a function $f$ in one real variable, to which we have black-box access, and we want to maximize it. Now a reasonable approach is to apply any standard algorithm for black-box mathematical optimization, e.g., grid search followed by hill-climbing, coordinate descent, gradient descent, Newton's method, or other methods.

It is also possible that some suitable criterion on $F,G$ might imply that $f$ has a nice property that makes it easy to maximize (e.g., it is increasing or something), and which might imply that your linear subset scan algorithm is a good approach. I have not thought about that carefully, but you might look at that direction.