Return to Answer

fixed broken MathJax

Source Link

edit approved Sep 19, 2014 at 14:06

1.3k
4
22
45

I found a paper by DB Neill, published in 2012, http://www.cs.cmu.edu/~neill/papers/jrssb2012.pdf‎ , which claims that if $F(A,B)$ is a function defined for posiivepositive inputs which is weakly increasing in $A$ for fixed $B$, and quasi-convex as a function of $A$ and $B$, then the optimal solution for

$\hbox{argmax}_I F( \sum_{i \in I} a_i, \sum_{i \in I} b_i})$$\hbox{argmax}_I F(\sum_{i\in I}a_i,\sum_{i\in I}b_i)$

(for positive $a_i,b_i$) is given by the subset of top $k$ pairs $(a_i,b_i)$ for some $k$ when pairs are sorted according to $a_i/b_i$ in descending order. However I believe I found a gap in the proof, and it seems that all subsets of size $1$ need to be considered in addition to all subsets of top $k$ pairs. The function $F(X,Y) = 1/Y$$F(X,Y)=1/Y$ gives such an example. But it is still a very fast "linear time subset scan" even if all subsets of size $1$ need to also be checked. Anyway, this is the most general example I've been able to find and it satisfies my desire to find "general properties" of objective functions where the sort-and-scan approach or something very similar works.

I found a paper by DB Neill, published in 2012, www.cs.cmu.edu/~neill/papers/jrssb2012.pdf‎ , which claims that if $F(A,B)$ is a function defined for posiive inputs which is weakly increasing in $A$ for fixed $B$, and quasi-convex as a function of $A$ and $B$, then the optimal solution for

$\hbox{argmax}_I F( \sum_{i \in I} a_i, \sum_{i \in I} b_i})$

(for positive $a_i,b_i$) is given by the subset of top $k$ pairs $(a_i,b_i)$ for some $k$ when pairs are sorted according to $a_i/b_i$ in descending order. However I believe I found a gap in the proof, and it seems that all subsets of size $1$ need to be considered in addition to all subsets of top $k$ pairs. The function $F(X,Y) = 1/Y$ gives such an example. But it is still a very fast "linear time subset scan" even if all subsets of size $1$ need to also be checked. Anyway, this is the most general example I've been able to find and it satisfies my desire to find "general properties" of objective functions where the sort-and-scan approach or something very similar works.

I found a paper by DB Neill, published in 2012, http://www.cs.cmu.edu/~neill/papers/jrssb2012.pdf‎, which claims that if $F(A,B)$ is a function defined for positive inputs which is weakly increasing in $A$ for fixed $B$, and quasi-convex as a function of $A$ and $B$, then the optimal solution for

$\hbox{argmax}_I F(\sum_{i\in I}a_i,\sum_{i\in I}b_i)$

(for positive $a_i,b_i$) is given by the subset of top $k$ pairs $(a_i,b_i)$ for some $k$ when pairs are sorted according to $a_i/b_i$ in descending order. However I believe I found a gap in the proof, and it seems that all subsets of size $1$ need to be considered in addition to all subsets of top $k$ pairs. The function $F(X,Y)=1/Y$ gives such an example. But it is still a very fast "linear time subset scan" even if all subsets of size $1$ need to also be checked. Anyway, this is the most general example I've been able to find and it satisfies my desire to find "general properties" of objective functions where the sort-and-scan approach or something very similar works.

Source Link

created Sep 16, 2013 at 20:54

user2566092

$\hbox{argmax}_I F( \sum_{i \in I} a_i, \sum_{i \in I} b_i})$

(for positive $a_i,b_i$) is given by the subset of top $k$ pairs $(a_i,b_i)$ for some $k$ when pairs are sorted according to $a_i/b_i$ in descending order. However I believe I found a gap in the proof, and it seems that all subsets of size $1$ need to be considered in addition to all subsets of top $k$ pairs. The function $F(X,Y) = 1/Y$ gives such an example. But it is still a very fast "linear time subset scan" even if all subsets of size $1$ need to also be checked. Anyway, this is the most general example I've been able to find and it satisfies my desire to find "general properties" of objective functions where the sort-and-scan approach or something very similar works.