Como dice Sushant, sin ninguna suposición sobre los pesos nada mejor que la relación de aproximación trivial es imposible bajo la suposición de que [matemática] P \ neq NP [/ matemática]. Por lo tanto, la suposición habitual que se hace es que los pesos siguen la desigualdad triangular. En otras palabras, para tres vértices [matemáticas] a, b, c [/ matemáticas] tenemos que [matemáticas] w (a, b) + w (b, c)> = w (a, c) [/ matemáticas] .
(1) Pesos simétricos : bajo esta suposición, tenemos la propiedad de que para dos vértices [matemática] a, b [/ matemática] el peso del borde del borde de a a b es el mismo que el peso de b a a. Para esta suposición, la aproximación más conocida es 3/2, que se debe a Christofides [1]. Hasta la fecha, esta sigue siendo la aproximación más conocida.
(2) Pesos asimétricos: eliminar el supuesto simétrico hace que el problema sea mucho más difícil. La primera aproximación conocida a este problema fue una aproximación [math] \ log_2 (n) [/ math] debido a Frieze, Galbiati y Maffioli [2]. Posteriormente, esto se mejoró en una serie de trabajos y finalmente se logró una aproximación de [matemáticas] 0.66 \ log_2 (n) [/ matemáticas] por Feige y Singh [3]. Luego esto se mejoró aún más a [matemáticas] O (\ log (n) / \ log \ log (n)) [/ matemáticas] en un trabajo innovador de Asadpour, Goemans, Madry, Oveis Gharan y Saberi [4]. Esta siguió siendo la aproximación más conocida a este problema hasta 2017. Un trabajo reciente de Svensson, Tarnawski y Vegh [5] ha afirmado finalmente romper esta barrera súper constante y obtener una aproximación O (1) a esta versión del problema. La constante es grande y aún no está cerca del valor conjeturado de 2 por Charikar, Goemans y Karloff [6]. ¡Sin embargo, este es un gran resultado!
- ¿Qué es exactamente la informática teórica? ¿Qué se investiga en él?
- ¿Cómo empiezo a explorar el campo de la lingüística como estudiante de informática?
- ¿Las publicaciones innovadoras tienden a ser publicadas por unos pocos o muchos autores?
- ¿Cuáles son buenos temas para una tesis de informática?
- ¿Cuáles son las limitaciones prácticas de la visión por computadora móvil?
[1] https: //pdfs.semanticscholar.org…
[2] https://www.math.cmu.edu/~af1p/T…
[3] Relaciones de aproximación mejoradas para recorridos y rutas de vendedores itinerantes en gráficos dirigidos
[4] https://www.cs.cmu.edu/~odonnell…
[5] https://arxiv.org/pdf/1708.04215…
[6] http://citeseerx.ist.psu.edu/vie…
