0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Your answer is not correct. You should look at $-x_1,...,-x_n$ if you want to maximize instead of minimizing the tour length. Inverting the distance can give you wrong answers. $\endgroup$
    – SKV
    Feb 12, 2014 at 8:49

1 Answer 1

0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .