What is the complexity of and how to go about solving the following task?
Given $a, b \in \mathbb{R}_+^n$ and $n \ge k\in\mathbb{N}$, find
$$ x_{\min} := \arg \min_{x \in \lbrace 0,1 \rbrace^n, x^T x = k} \frac{x^Ta}{x^Tb} $$
$\begingroup$
$\endgroup$
4
asked May 27, 2019 at 11:07
-
$\begingroup$ Isn't it just $\min \frac{a_i}{b_i}$, in view of the inequality $\frac{\sum a_i}{\sum b_i} \geq \min \frac{a_i}{b_i}$? $\endgroup$– WhatsUpMay 27, 2019 at 11:54
-
$\begingroup$ After further looking at your question, I notice that $k$ is actually a fixed integer... Perhaps it'll be better to emphasize it in your statement? $\endgroup$– WhatsUpMay 27, 2019 at 11:56
-
$\begingroup$ Question edited accordingly $\endgroup$– Manfred WeisMay 27, 2019 at 12:03
-
1$\begingroup$ The naive algorithm is 1) put $z=(\sum_{i=1}^k a_i)/(\sum_{i=1}^kb_i)$; 2) sort the indices so that $a_i-zb_i$ is non-decreasing; 3) if the sorting didn't change anything, output $z$, else go to (1); That is guaranteed to terminate after $n^2$ cycles (so the total complexity is at most $n^3\log n$) but, probably, it stops much sooner for most data. Of course, there may be much better ideas. This is just to set the level of triviality. $\endgroup$– fedjaMay 27, 2019 at 13:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Take a look at this question: Optimization algorithm sought, and its answer by David Eppstein.
This is the way I understand it. The first part in that comes from Dinkelbach's theorem on fractional optimization. The second part is just geometry of lines in 2D, followed by a golden section search.
