assume p not equal to np 1- it\'s known that the general traveling salesman prob
ID: 3618972 • Letter: A
Question
assume p not equal to np 1- it's known that the general traveling salesman problemis np-hard use this fact to show that the taveling salesman problemwith the triangle inequality property is still np hard 2- is the approximation traveling salesman problem with thetriangle inequality np hard for every approximation ratio ( juststate the result) 3- is the approximation general traveling salesman problem nphard for every approximation ratio ( prove it in details) 1- it's known that the general traveling salesman problemis np-hard use this fact to show that the taveling salesman problemwith the triangle inequality property is still np hard 2- is the approximation traveling salesman problem with thetriangle inequality np hard for every approximation ratio ( juststate the result) 3- is the approximation general traveling salesman problem nphard for every approximation ratio ( prove it in details)Explanation / Answer
The answer : We transform an instance of travelling salesman problem toanother one that satisfies the triangle inequality. Let k be theweight of all edges, by adding k to all edges we obtain an instancethat satisfies the triangle inequality. The optimal tour remains unchanged, since all tours have thesame number of edges, we therefore simply added nk to alltours. This does not contradict the theorem that if p not equalto np . then for every constant p >= 1 , there is no polynomialtime approximation algorithm with ratio bound p for the generalTSP. since the transformed problem does not gives ratio bound p forthe original problem.2- is the approximation traveling salesman problem with thetriangle inequality np hard for every approximation ratio ( juststate the result) The answer :NO . it is not . because , APPROX-TSP_TOUR has a polynomial time2-approximation algorithm for the TSP with triangleinequality.
3- is the approximation general traveling salesman problem nphard for every approximation ratio ( prove it in details) The answer: YES , If p not equal to np . then for every constant p>= 1 , there is no polynomial time approximation algorithm withratio bound p for the general TSP. Proof: Let G=(V,E) be an instance of HAM-CYCLE , we defineG'=(V,E') to be complete graph on V , define the cost for the edge(u,v) in E' as c(u,v) = { 1 if (u,v) is in E P|V| + 1 otherwise so , (P|V| + 1)+(|V| - 1) = P|V| + |V| >P|V| because , edges does not in G are so costly there is a gap ofP|V| between the cost of a tour that is HAM_CYCLE ( cost |V|) andall other tours ( cost at least P|V| + |V|) . if we apply the approximation algorithm A to TSP , because Ais guarnteed to return a tour of cost no more p times the cost ofthe optimal tour . SO if G has HAM_CYCLE it returns it if not it returns a tour of cost more than P|V| times so , this algorithm can be solve HAM_CYCLE in polynomialtime.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.