An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem
URL to paper on conference site
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60990 https://orcid.org/0000-0003-0536-0323 https://orcid.org/0000-0002-0520-1165 |
| _version_ | 1811089748800831488 |
|---|---|
| author | Asadpour, Arash Goemans, Michel X. Madry, Aleksander Gharan, Shayan Oveis Saberi, Amin |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Asadpour, Arash Goemans, Michel X. Madry, Aleksander Gharan, Shayan Oveis Saberi, Amin |
| author_sort | Asadpour, Arash |
| collection | MIT |
| description | URL to paper on conference site |
| first_indexed | 2024-09-23T14:24:05Z |
| format | Article |
| id | mit-1721.1/60990 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:24:05Z |
| publishDate | 2011 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/609902022-10-01T21:05:18Z An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem Asadpour, Arash Goemans, Michel X. Madry, Aleksander Gharan, Shayan Oveis Saberi, Amin Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Goemans, Michel X. Goemans, Michel X. Madry, Aleksander URL to paper on conference site We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability. National Science Foundation (U.S.) (Fulbright Science and Technology Award, contract CCF- 0829878) National Science Foundation (U.S.) (contract CCF- 0829878) United States. Office of Naval Research (ONR grant N00014-05-1-0148) 2011-02-18T19:51:40Z 2011-02-18T19:51:40Z 2010-01 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/60990 Asadpour, Arash, et al. "An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem." Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 17-19,2010, Hyatt Regency Austin, Austin, TX. © 2010 SIAM. https://orcid.org/0000-0003-0536-0323 https://orcid.org/0000-0002-0520-1165 en_US http://www.siam.org/proceedings/soda/2010/SODA10_032_asadpoura.pdf Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Asadpour, Arash Goemans, Michel X. Madry, Aleksander Gharan, Shayan Oveis Saberi, Amin An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title | An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title_full | An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title_fullStr | An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title_full_unstemmed | An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title_short | An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem |
| title_sort | o log n log log n approximation algorithm for the asymmetric traveling salesman problem |
| url | http://hdl.handle.net/1721.1/60990 https://orcid.org/0000-0003-0536-0323 https://orcid.org/0000-0002-0520-1165 |
| work_keys_str_mv | AT asadpourarash anolognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT goemansmichelx anolognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT madryaleksander anolognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT gharanshayanoveis anolognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT saberiamin anolognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT asadpourarash olognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT goemansmichelx olognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT madryaleksander olognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT gharanshayanoveis olognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem AT saberiamin olognloglognapproximationalgorithmfortheasymmetrictravelingsalesmanproblem |