Return to Question

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs defined by $I^* \subseteq Y$, which maximizes an objective of the form

$\max_{I \subseteq Y} F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs defined by $I^* \subseteq Y$, which maximizes an objective of the form

$\max_{I \subseteq Y} F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary positive strictly increasing $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Given a multi-set of pairs $(a,b)$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs $((a_i,b_i))_{i \in I}$ which maximizes an objective of the form

$F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs defined by $I^* \subseteq Y$, which maximizes an objective of the form

$\max_{I \subseteq Y} F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Given a multi-set of pairs $(a,b)$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs $((a_i,b_i))_{i \in I}$ which maximizes an objective of the form

$F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Given a multi-set of pairs $(a,b)$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs $((a_i,b_i))_{i \in I}$ which maximizes an objective of the form

$F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.