Consider the Travelling Salesman Problem:
Given N cities connected by edges of varying weights. Given a city A what is the shortest path for visiting all the cities exactly once that returns back to A
and the Max Travelling Salesman Problem:
Given N cities connected by edges of varying weights. Given a city A what is the largest path for visiting all the cities exactly once that returns back to A
Notice the following: If we take all the edge lengths of regular Travelling Salesman and we compute their reciprocals for example if we have edge lengths: 1, 2, 3 we form a new problem with corresponding edges 1, 1/2, 1/3 we can then solve regular Travelling Salesman with Max Travelling salesman.
Does this work?
An equivalent notion is the following:
Given a set of numbers
$Q = {x_1, x_2, x_3 ... x_n}$
if a k element minimum of the set is
${y_1, y_2, y_3 ... y_k}$
such that $y_i$ are all members of Q
Then:
Given a set of numbers
$Q' = {\frac{1}{x_1},\frac{1}{x_2},\frac{1}{x_3}... \frac{1}{x_n}}$
The k element maximum of the set is:
${\frac{1}{y_1},\frac{1}{y_2},\frac{1}{y_3}... \frac{1}{y_n}}$
^how do you prove that?
Here is one solution I believe
Take the set $Q = x_1,x_2,x_3...x_n$
And sort it in ascending order
Now the k minimum of the set is simply the first k elements since those are the k smallest elements.
Now consider the number $\frac{1}{x_i}$
If $x_i > 0$ then as $x_i ==> \infty$ $\frac{1}{x_i} ==> 0$
Therefore if we assume that $Q$ contains only positive elements, then the k element maximum of the set
${\frac{1}{x_1},\frac{1}{x_2},\frac{1}{x_3}...\frac{1}{x_n}}$
are the reciprocals of the k element minimum of the set
$Q = x_1,x_2,x_3...x_n$