1
$\begingroup$

I have a list of objects with $N$-dimensional criteria (actually hotels in my case). Now I'd like to optimize the order of the criteria by which I filter to spent the least time on some evaluation process per object. Each property $i$ takes a fixed time $t_i$ to evaluate per object, while it will reduce the total amount of considered objects by a factor $q_i$. Which order will give me the least total time of evaluation?

I got as far as saying I need to minimize

$((t_{N}q_{N-1}+t_{N-1})q_{N-2}+t_{N-2})q_{N-3}+t_{N-3}\dotsb\to\text{min}$

where the indices now represent a new fixed permutation! Which permutation would that be?

Any ideas?

EDIT: If it's any help one can of course also write

$\begin{pmatrix} q_1 & t_1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix} q_2 & t_2 \\ 0 & 1 \end{pmatrix}\dotsb\begin{pmatrix} q_N & t_N \\ 0 & 1 \end{pmatrix}\begin{pmatrix} 0\\ 1 \end{pmatrix}\to\text{min}$

I'm hoping for an algorithm that assigns "efficiencies" to all criteria and states that I should order all steps by efficiency.

  • 0
    Meanwhile I tried what happens if you require that neighboring operations are locally optimal and it seems the solution is to sort ascending by $t/(1-q)$.2012-08-19

0 Answers 0