Complete Weighted Graph G, Finding Weights and one Machine

Question

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?

Selfdrive

Answer 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.

Batey

"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? – Selfdrive

@Selfdrive - 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. – Batey

@IVlad, can we say surely (3) is true or not ? – Selfdrive

@Selfdrive (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. – Batey

in this file he say' w--> real ! – Selfdrive

@IVlad, please be clear, if you want choose one of this option, which should be select by you ? – Selfdrive

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. – Batey

my last question is why this file does not mentioned real vlue and say O(log n)? – Selfdrive

The file you are referencing seems to be dealing with integers, so things are clearer in that case. – Batey

in example he wrote : E -> Reals – Selfdrive

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. – Batey

it means again (3) is True definitely ?:) i think this assumption in my question is true. – Selfdrive

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. – Batey

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. – Hydroxy

@amit, you didnt agree with (3) ? – Selfdrive

@Selfdrive 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. – Hydroxy

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 ? – Selfdrive

@Selfdrive 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) – Hydroxy

my last question is, if you strict to choose one of these option, which one is selected by you ? :) thanks. @amit. – Selfdrive

@Selfdrive (2) as described in the original thread's accepted (and editted) answer. – Hydroxy

@amit, i talk to professor, that wrote this PDF file mentioned in my question, if you have time, please talk to me. – Selfdrive

@Selfdrive I added another clarification to the prof's answer chat.stackoverflow.com/rooms/73032/… I – Hydroxy

so I conclude until now, (b) is the best option. @Hydroxy – Selfdrive

@Hydroxy Is there some misunderstanding? For the graph you give as an example above, the optimum is 1, not 2/3. – Palaeobotany

@Palaeobotany no it's the hamiltonian path 1->2->3 which costs 1\3+1\3=2\3 – Hydroxy