loading...
On the Integrality Ratio for Asymmetric TSP
Rome, Italy October 17-October 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.4545th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Moses Charikar, Michel X. Goemans, Howard Karloff, "On the Integrality Ratio for Asymmetric TSP," Foundations of Computer Science, Annual IEEE Symposium on, pp. 101-107, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2004.45,
author = {Moses Charikar and Michel X. Goemans and Howard Karloff},
title = {On the Integrality Ratio for Asymmetric TSP},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2004},
issn = {0272-5428},
pages = {101-107},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.45},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - On the Integrality Ratio for Asymmetric TSP
SN - 0272-5428
SP101
EP107
A1 - Moses Charikar,
A1 - Michel X. Goemans,
A1 - Howard Karloff,
PY - 2004
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Moses Charikar, Princeton University
Michel X. Goemans, Massachusetts Institute of Technology
Howard Karloff, AT&T Labs
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.
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
Usage of this product signifies your acceptance of the Terms of Use.