Estoy buscando resultados de dureza en la coloración de vértices de gráficos con grado acotado. Dado un gráfico , sabemos que para cualquier ϵ > 0 , es difícil aproximar χ ( G ) dentro de un factor de | V | 1 - ϵ a menos que NP = ZPP [ 1 ]. Pero, ¿qué pasa si el grado máximo de G está limitado...
Como es bien sabido, los problemas de optimización de NP-hard pueden tener muchas relaciones de aproximación diferentes, que van desde tener un PTAS hasta no ser aproximable dentro de ningún factor. En el medio, tenemos varias constantes, , p o l y ( n ) , etc.O ( logn )O(logn)O(\log n)p o l y( n...
Los juegos de dos rondas y una ronda (2P1R) son una herramienta esencial para la dureza de la aproximación. Específicamente, la repetición paralela de juegos de una ronda de dos probadores ofrece una forma de aumentar el tamaño de una brecha en la versión de decisión de un problema de aproximación....
Para un gráfico dado , el Problema del separador pregunta si existe un conjunto de vértices o bordes de pequeña cardinalidad (o peso) cuya eliminación separa G en dos gráficos disjuntos de tamaños aproximadamente iguales. Esto se llama el Problema del separador de vértices cuando el conjunto...
Estoy buscando una clase de complejidad que se relacione con APX como BPP se relaciona con P. Ya he hecho la misma pregunta aquí , pero tal vez TCS sería una ubicación más fructífera para las respuestas. La razón de la pregunta es que, en problemas prácticos, a menudo es necesario encontrar...
¿Qué se sabe actualmente sobre la aproximabilidad del problema del género? Una búsqueda preliminar me dice que una aproximación de factor constante es trivial para gráficos suficientemente densos, y se ha descartado un algoritmo de aproximación . ¿Esta información está actualizada o se conocen...
No he podido encontrar en la literatura una caracterización precisa de la desaparición de la brecha de dualidad SDP. O, ¿cuándo se mantiene la "dualidad fuerte"? Por ejemplo, cuando uno va y viene entre Lasserre y SOS SDP, en principio uno tiene una brecha de dualidad. Sin embargo, de alguna...
Escuché de un resultado en el color aproximado del gráfico, pero no puedo encontrar la fuente. El resultado es: Para cada constante existe una suficientemente grande como para que colorear un gráfico coloreable con colores sea NP-duro.hhhkkkkkkh khkhk ¿Podría alguien señalarme el documento...
Muchos aquí probablemente estén al tanto de los límites inferiores súper lineales recientes de Alon para redes en un entorno geométrico natural [PDF] . Me gustaría saber qué implica, en todo caso, un límite inferior acerca de la aproximación de los problemas asociados de Set Cover / Hitting Set....
¿Es difícil apx aproximar el número cromático fraccionario en gráficos de grados
Considere el problema del conjunto dominante en gráficos generales, y sea el número de vértices en un gráfico. Un algoritmo de aproximación codicioso ofrece una garantía de aproximación del factor 1 + log n , es decir, es posible encontrar en el tiempo polinómico una solución S tal que | S | ≤ ( 1...
Estoy estudiando la Conjetura de juegos únicos y la famosa reducción a Max-Cut de Khot et al. Desde su artículo y en otras partes de Internet, la mayoría de los autores usan (lo que para mí es) una equivalencia implícita entre la reducción MAX-CUT y la construcción de pruebas particulares para...
En el problema de la camarilla plantada, uno debe recuperar una kkk camarilla plantada en un gráfico aleatorio Erdos-Renyi ( n , p )G(n,p)sol(norte,pags)G(n,p) . Esto se ha visto principalmente para p=12pags=12p=\frac{1}{2} , en cuyo caso se sabe que puede resolverse en tiempo polinómico...
Considere el problema clásico # P-complete # 3SAT, es decir, contar el número de valoraciones para hacer que un 3CNF con nnn variables sea satisfactoria. Estoy interesado en la aproximabilidad aditiva . Claramente, hay un algoritmo trivial para lograr2n−12n−12^{n-1}error 2 n - 1 , pero...
Sea una familia de subconjuntos de elementos de un universo finito de objetos. Una familia de subconjuntos -elemento de , con , es una - hitting-set de si, para cada existe al menos un conjunto tales que .FFFdddUUUHHHkkkUUU1≤k<d1≤k<d1 \le k < d(k,d)(k,d)(k,d)FFFV∈FV∈FV \in FW∈HW∈HW \in...
En el problema de Max-Cut , se busca un subconjunto S de vértices de un gráfico simple no dirigido dado de modo que el número de aristas entre S y el complemento de S sea lo más grande posible. Max-Cut es APX-complete en gráficos de grado acotado [PY91], y de hecho APX-complete en gráficos cúbicos...
Estoy tratando de mostrar que un cierto problema no es posible por una reducción de la cobertura establecida. Mi reducción transforma una instancia con conjuntos de tierra de conjuntos de tamaño nnn y mmm en una instancia de mi problema donde un determinado parámetro rrr es de tamaño...
Me pregunto si el siguiente problema tiene un nombre o algún resultado relacionado con él. Sea un gráfico ponderado donde denota el peso del borde entre y , y para todos , . El problema es encontrar un subconjunto de vértices que maximice la suma de los pesos de los bordes adyacentes a ellos:...
Tratar de encontrar la solución óptima para WEIGHTED-MAX-3SAT, la versión ponderada del problema de optimización 3-SAT, es NP-hard. De hecho, incluso aproximar la versión no ponderada de MAX-SAT arbitrariamente es probablemente NP-duro por el teorema de PCP. Un algoritmo canónico para aproximar...
Tengo algunas preguntas sobre la conjetura de Quantum PCP: ¿Cuál es la declaración de la conjetura de PCP cuántica? ¿Qué implicaciones tendría el teorema de PCP Quantum para la simulación de hamiltonianos? ¿Se cree que la adopción de la prueba de Irit Dinur del teorema clásico de PCP puede...