3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.