پديد آورنده :
نعمت الهي، شميسا
عنوان :
الگوريتم هاي تقريبي مساله فروشنده دوره گرد
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
رياضي كاربردي
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي
صفحه شمار :
[پانزده]، [۸۴]ص.: مصور
استاد راهنما :
رامين جوادي
واژه نامه :
انگليسي به فارسي، فارسي به انگليسي
توصيفگر ها :
مساله گراف , الگوريتم تقريبي STSP , الگوي تقريبي ATSP
استاد داور :
زينب مالكي، محسن جانثاري
تاريخ ورود اطلاعات :
1396/08/13
چكيده انگليسي :
Approximation Algorithms for the Traveling Salesman Problem Shamisa Nematollahi shamisa nematollahi@math iut ac ir 2017 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Ramin Javadi rjavadi@cc iut ac ir 2010 MSC Keywords Traveling salesman problem Thin tree Approximation algorithm Integrality gap Linear programming Metric TSP Relaxation and rounding method AbstractThe traveling salesman problem TSP is one of the most important combinatorial optimization prob lems The salesman wants to visit some cities and he wants to visit each city exactly once and returnto the begining city minimize the total cost of the trip At rst one may to express the equivalenceof the problem in graph theory we are given a complete graph G V E and the cost functionc V V R 0 such that each vertex represents a city and the cost function c speci es thecost of going from each city to another one The goal is to nd a minimum cost tour that visits everyvertex exactly once i e a Hamiltonian cycle with minimum total cost Karp proved that the problem is NP complete in 1972 So we are interested in nding goodapproximation algorithms for TSP An approximation algorithm for an optimization problem is apolynomial time algorithm that for all instances of the problem produces a solution whose value iswithin a factor of of the value of an optimal solution Unfortunately Sahni and Gonzalez in 1976proved that it is NP complete to approximate TSP with a factor Consequently we de ne a specialcase of the problem is de ned named metric TSP TSP is metric if for any three vertices u v w V the triangle inequality is always satis ed i e c u v c v w c u w The goal is to nd a minimumcost tour that visits every vertex exactly once or equivalently at least once because of the triangleinequality So aim to nd an Eulerian connected subgraph of G of the smallest cost 3 Christo des gave an approximation algorithm with factor for metric TSP in 1976 This algorithm 2was the rst approximation algorithm for metric TSP This algorithm at rst nds a minimum cost
استاد راهنما :
رامين جوادي
استاد داور :
زينب مالكي، محسن جانثاري
