Preguntas sobre algoritmos que resuelven problemas hasta algún error acotado.
Leí en muchos lugares que algunos problemas son difíciles de aproximar (es NP-difícil aproximarlos ). Pero la aproximación no es un problema de decisión: la respuesta es un número real y no Sí o No. Además, para cada factor de aproximación deseado, hay muchas respuestas correctas y muchas...
Estoy buscando un algoritmo para distribuir valores de una lista para que la lista resultante esté lo más "equilibrada" o "distribuida de manera uniforme" posible (entre comillas porque no estoy seguro de que estas sean las mejores formas de describirla ... más adelante proporcionaré una forma de...
Me gustaría comenzar la pregunta diciendo que soy programador y que no tengo muchos antecedentes en teoría de la complejidad. Una cosa que he notado es que si bien muchos problemas son NP completos, cuando se extienden a problemas de optimización, algunos son mucho más difíciles de aproximar que...
He estudiado algo sobre la complejidad de Kolmogorov , leí algunos artículos y libros de Vitanyi y Li y usé el concepto de Distancia de compresión normalizada para verificar la estilometría de los autores (identifique cómo cada autor escribe algunos textos y documentos grupales por su...
Tengo un problema de decisión NP-completo. Dada una instancia del problema, me gustaría diseñar un algoritmo que genere SÍ, si el problema es factible, y, de lo contrario, NO. (Por supuesto, si el algoritmo no es óptimo, cometerá errores). No puedo encontrar ningún algoritmo de aproximación para...
He estado mirando este sitio y dice que la gente encontró soluciones para recorridos TSP que son solo 0.031% más altos que el recorrido óptimo. Sin encontrar el recorrido óptimo, ¿cómo saben qué longitud se supone que debe
El problema del ancho de banda mínimo es encontrar un orden de los nodos del gráfico en la línea entera que minimiza la distancia más grande entre dos nodos adyacentes. El problema de decisión es NP-completo incluso para árboles binarios. Resultados de complejidad para la minimización del ancho...
Por lo que leí en el preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Esta es la definición de PTAS : Un esquema de aproximación de tiempo polinomial ( PTAS ) para el...
Dado el hecho de que enumeración de la ruta s - t es un problema # P-completo, ¿podría haber métodos eficientes que calculen (o al menos aproximen) la longitud promedio de la ruta s - t sin enumerarlos? ¿Qué pasa si se permite a los caminos volver a visitar los vértices?ssstttsssttt Los...
Según el artículo de Wikipedia sobre esquemas de aproximación de tiempo polinomial : Todos los problemas en FPTAS son manejables de parámetros fijos. Este resultado me sorprende: estas clases parecen ser totalmente diferentes entre sí. FPTAS caracteriza los problemas por su facilidad de...
¿Qué es un algoritmo de aproximación de bicriteria? Esto sigue apareciendo en el caso de la agrupación de flujo de datos. ¿Está esto relacionado con la optimización de objetivos múltiples? Aquí es donde lo encontré: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. El documento trata sobre una...
Sea un problema de conteo que se sabe que es # -Complete .ΠΠ\PiPPP ¿ Implica que es duro (es decir, no existe PTAS para el problema a menos que
El problema es el siguiente: Tenemos una matriz / cuadrícula bidimensional de números, cada uno representa algún "beneficio" o "beneficio". También tenemos dos enteros fijos y (para "ancho" y "altura"). Y un entero fijo .wwwhhhnnn Ahora deseamos superponer rectángulos de dimensiones en la...
Sea una función bastante agradable (p. Ej., Continua, diferenciable, no demasiados máximos locales, tal vez cóncavos, etc.). Quiero encontrar un máximo de f : un valor x ∈ R d que haga que f ( x ) sea lo más grande posible.F: Rre→ Rf:Rd→Rf:\mathbb{R}^d \to \mathbb{R}Fffx ∈ Rrex∈Rdx \in...
Deje que LϵLϵL_\epsilon sea el lenguaje de todas las fórmulas 222 -CNF φφ\varphi , de modo que pueda satisfacerse al menos ( 12+ ϵ )(12+ϵ)(\frac{1}{2}+\epsilon) de las cláusulas de φφ\varphi . Necesito demostrar que existe ϵ′ϵ′\epsilon' st LϵLϵL_\epsilon es N PNP\mathsf{NP} -hard para cualquier...
Dado un programa entero (binario) de la forma:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Tenga en cuenta que el...
Tengo un problema con respecto a la siguiente situación. Tengo dos conjuntos de números como este: index/pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Array 1(i): 1 2 3 4 7 5 4 3 7 6 5 1 2 3 4 2 Array 2(j): 4 4 8 10 10 7 7 10 10 11 7 4 7 7 4 ahora supongamos que la segunda matriz es muy difícil...
¿El 2 en un algoritmo de aproximación 2 significa que la solución está dentro de 2 * OPT u OPT /
Digamos que encontré un algoritmo de aproximación de 2 para un problema determinado y quiero mostrar que el análisis es estricto. ¿Necesito ahora encontrar un ejemplo de tamaño genérico o es suficiente para mostrar que tengo un ejemplo de tamaño para el cual el algoritmo produce...
Tengo un problema logístico que puede verse como una variante de TSPTSP\text{TSP}. Es tan natural, estoy seguro de que se ha estudiado en la investigación de operaciones o algo similar. Aquí hay una forma de ver el problema. Tengo almacenes en el plano cartesiano. Hay un camino desde un almacén a...