Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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|cite|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


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

Browse other questions tagged or ask your own question.