Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I can't think of an algorithm to do this, but a scheduling algorithm should do the job. Perhaps of an alternative of a general job shop problem heuristic may be appropriate. –  Daryl Aug 19 '12 at 8:12
    
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)$. –  Gerenuk Aug 19 '12 at 10:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.