Levels Tought:
Elementary,Middle School,High School,College,University,PHD
Teaching Since: | May 2017 |
Last Sign in: | 308 Weeks Ago |
Questions Answered: | 66690 |
Tutorials Posted: | 66688 |
MCS,PHD
Argosy University/ Phoniex University/
Nov-2005 - Oct-2011
Professor
Phoniex University
Oct-2001 - Nov-2016
The bottleneck traveling-salesman problem is the problem of finding the hamiltonian cycle such that the cost of the most costly edge in the cycle is minimized. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial-time approximation algorithm with approximation ratio 3 for this problem. (Hint: Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)
Hel-----------lo -----------Sir-----------/Ma-----------dam-----------Tha-----------nk -----------You----------- fo-----------r u-----------sin-----------g o-----------ur -----------web-----------sit-----------e a-----------nd -----------and----------- ac-----------qui-----------sit-----------ion----------- of----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n.P-----------lea-----------se -----------pin-----------g m-----------e o-----------n c-----------hat----------- I -----------am -----------onl-----------ine----------- or----------- in-----------box----------- me----------- a -----------mes-----------sag-----------e I----------- wi-----------ll