Advanced Search
CS Search Google Search
Subscribers, please login

Published Articles >> Table of Contents >> Abstract

45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)   pp. 101-107
On the Integrality Ratio for Asymmetric TSP

Full Article Text: Download PDF of full textBuy this articleGet full text from IEEE Xplore

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.45
Send link to a friend

Abstract
We improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP (with triangle inequality) from 4/3 to 2.
Additional Information

Citation:  Moses Charikar, Michel X. Goemans, Howard Karloff, "On the Integrality Ratio for Asymmetric TSP," focs, pp. 101-107,  45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04),  2004

Similar Articles

Abstract Contents
Abstract
Citation




Free access to

  • Abstracts
  • Selected PDFs

Electronic subscribers login to:

  • Access HTML/PDFs of full text articles

Subscription information

Get a Web account

PDFs require Adobe Acrobat Reader.

Peer Review Notice

Give us Feedback