CODEWITHSUNDEEP
algorithmgraphcomputation-theorynphamiltonian-cycle
user4249446
user4249446

Reputation:

Complete Weighted Graph G, Finding Weights and one Machine

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?

Upvotes: 6

Views: 374

Answers (1)

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 1

Related Questions