6

I read a lot about Complete Weighted Graph and Hamiltonian Tour topics in this site that asked by one of users, ask a lots of staff in my university, but couldn't get to a good answer, I change an important part of this question as follows:

Problem A: Given a Complete Weighted Graph G, find weights of Hamiltonian Tour with minimum weight.

Problem B: Given a Complete Weighted Graph G and Real Number R, does G have a Hamiltonian Tour with weight at most R?

Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.

  1. We cannot do this, because there is uncountable state.

  2. O(|E|) times

  3. O(lg m) times

  4. because A is NP-Hard, This is cannot be done.

I read this file, on page 2 he wrote:

a) optimization problem (in the strict sense): find an optimal solution

b) evaluation problem: determine the value of an optimal solution

c) bound problem: given a bound B, determine whether the value of an optimal solution is above or below B.

on the next two paragraph

To exploit c) in solving b), we use the fact that the possible values of a combinatorial problem are usually discrete and can be taken to be integers. Assume we can solve the bound problem c) within time T. For the corresponding evaluation problem b) one usually knows a priori that the value lies within a certain range [L, U] of integers. Using binary search, we solve the evaluation problem with log | U - L | calls to the bound problem c), and hence in time T log | U - L |.

and in the next he wrote:

Ex: TSP on weighted graph Kn = (V, E, w: E -> Reals), |V| = n, |E| = n-choose-2. Use c) to solve b). A tour or Hamiltonian cycle in a graph of n vertices has exactly n edges. Thus, the sum S of the n longest edges is an upper bound for the length of the optimal tour. On the other hand, the sums of all m choose-n subsets of n edges is a finite set of numbers, and the minimal non-zero difference d among two of these numbers defines the granularity of the tour lengths. Two distinct tours either have the same value, or their lengths differ by at least d. Thus, a binary search that computes log( S / d) bound problems determines the length (value) of an optimal tour.

My question is can we adapt this solution to choose (3) in this way?

Community
  • 1
  • 1

1 Answers1

1

Suppose there is a machine that solves B. How many times can we call B (each time G and Real number R are given),to solve problem A with that machine? Suppose the sum of Edges in G up to M.

O(log M).

Pick a = 0, b = M.

  1. set R = (a + b) / 2. Solve B with this R.

  2. The result is True

    Then there is a Hamiltonian Tour with weight at most R. Is there one for a tighter upper bound? Set b = R and repeat to find out (go to 1).

  3. The result is False

    Then there is no Hamiltonian Tour with weight at most R: the minimum weight is larger. Set a = R and repeat (go to 1).

This is the binary search algorithm.

While it is true in theory that this algorithm would not work on all real numbers (especially irrational ones), you cannot have irrational numbers in practice. A computer can only represent approximations of irrational numbers anyway, so you can use binary search to get an approximation that is good to as many decimals as you are willing to run the algorithm for.

For example, if one of your edges had the value pi, you would have to settle for an approximation of it to begin with, since the mathematical constant pi has an infinite number of digits. So no matter what algorithm you used, you would have some level of precision issues.

Community
  • 1
  • 1
IVlad
  • 43,099
  • 13
  • 111
  • 179
  • "as some people noted that you cannot apply binary search in an uncountable set. Since we are talking about real numbers, we cannot apply binary search in the range [0-M]" is it false? –  Mar 15 '15 at 19:16
  • 2
    @user4249446 - it's true in theory, but you cannot have irrational numbers in practice. A computer can only represent approximations of irrational numbers anyway, so you can use binary search to get an approximation that is good to as many decimals as you are willing to run the algorithm for. – IVlad Mar 15 '15 at 19:18
  • 2
    @IVlad, can we say surely (3) is true or not ? –  Mar 15 '15 at 19:31
  • @user4249446 (3) is doable from an engineering POV: I can implement an algorithm that gets you an approximation in that time. If it must work for real numbers, then (3) doesn't work, and personally I can't help with that variation of the problem. – IVlad Mar 15 '15 at 19:35
  • in this file he say' w--> real ! –  Mar 15 '15 at 19:36
  • @IVlad, please be clear, if you want choose one of this option, which should be select by you ? –  Mar 15 '15 at 19:39
  • I would choose (3) in a Computer Science context, like my answer explains. I would choose "let me go home" in a pure math context. – IVlad Mar 15 '15 at 19:42
  • my last question is why this file does not mentioned real vlue and say O(log n)? –  Mar 15 '15 at 19:44
  • The file you are referencing seems to be dealing with integers, so things are clearer in that case. – IVlad Mar 15 '15 at 19:46
  • in example he wrote : E -> Reals –  Mar 15 '15 at 19:47
  • He also says `On the other hand, the sums of all m choose-n subsets of n edges is a finite set of numbers`. This is the set he is binary searching on. – IVlad Mar 15 '15 at 19:54
  • 1
    it means again (3) is True definitely ?:) i think this assumption in my question is true. –  Mar 15 '15 at 19:58
  • No, from a purely mathematical standpoint that doesn't consider the physical limitations of computers, (3) is not true (at least my algorithm isn't). Otherwise, it is true. It's up to you to decide if you want to view this as a pure math problem or as a practical problem. – IVlad Mar 15 '15 at 20:00
  • Note that this answer was discussed thoroughly in the linked thread, with most participants agreeing it's a bad fit due to the theoretical aspect of this problem. The order of convergence however is exponential, and you can get to any arbitrary bound on the answer pretty quickly. – amit Mar 15 '15 at 21:58
  • @amit, you didnt agree with (3) ? –  Mar 16 '15 at 07:37
  • 2
    @user4249446 I had my doubts, but at the end, I didn't. It has flaws when dealing with theoretical problem, for example - consider the graph V={a,b,c} and `E={(a,b,1/3),(b,c,1/3), (a,c,1/3)}`. In the binary search solution you will set as upper limit `M=1`, and start binary search between `0` and `1`, but at each step, your current number is `x/2^-i` for some `x,i`. You are not going to be able to find 2/3 with this. You can however come as close as you wish to, in exponential rate, but you will never find 2/3 exactly. – amit Mar 16 '15 at 08:00
  • okey, please check my inference, if we see this solution in computer science, the (3) is the right, but in practical it has flaws. am i right ? –  Mar 16 '15 at 08:44
  • @user4249446 Computer science is theoretical, and in computer science, (3) seems to be incorrect (or at least I don't see a solution that does it in the desired time complexity, only an approximation) – amit Mar 16 '15 at 08:53
  • my last question is, if you strict to choose one of these option, which one is selected by you ? :) thanks. @amit. –  Mar 16 '15 at 09:06
  • @user4249446 (2) as described in the original thread's accepted (and editted) answer. – amit Mar 16 '15 at 09:07
  • @amit, i talk to professor, that wrote this PDF file mentioned in my question, if you have time, please talk to me. –  Mar 19 '15 at 09:56
  • @user4249446 I added another clarification to the prof's answer http://chat.stackoverflow.com/rooms/73032/room-for-amit-and-user4249446 I – amit Mar 19 '15 at 10:33
  • so I conclude until now, (b) is the best option. @amit –  Mar 19 '15 at 11:21
  • @amit Is there some misunderstanding? For the graph you give as an example above, the optimum is 1, not 2/3. – Codor Apr 09 '15 at 22:15
  • @Codor no it's the hamiltonian path 1->2->3 which costs 1\3+1\3=2\3 – amit Apr 10 '15 at 07:02