preguntas generales sobre cómo seleccionar un mejor elemento de un conjunto de alternativas disponibles.
Estoy bastante confundido por la literatura de optimización continua y la literatura de TCS sobre qué tipos de programas matemáticos (continuos) (MP) se pueden resolver de manera eficiente y cuáles no. La comunidad de optimización continua parece afirmar que todos los programas convexos se pueden...
En mi educación en ciencias de la computación, noto cada vez más que la mayoría de los problemas discretos son NP completos (al menos), mientras que la optimización de problemas continuos es casi siempre fácil de lograr, generalmente a través de técnicas de gradiente. ¿Hay excepciones a...
Lo que se sabe sobre la complejidad del siguiente problema: Dado: números racionales .x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n Salida: enteros .y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n Objetivo: minimizar donde∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i < j...
Las computadoras cuánticas son muy buenas para distribuciones de muestreo que no sabemos cómo muestrear usando computadoras clásicas. Por ejemplo, si f es una función booleana (de a - 1 , 1 ) que se puede calcular en tiempo polinómico, entonces con computadoras cuánticas podemos muestrear...
Considere los problemas de optimización de la siguiente forma. Sea f(x)f(x)f(x) una función computable en tiempo polinómico que mapea una cadena xxx en un número racional. El problema de optimización es este: ¿cuál es el valor máximo de f(x)f(x)f(x) sobre cadenas de nnn bits xxx ? Digamos que tal...
Estoy interesado en el problema de empacar copias idénticas de rectángulos (2 dimensiones) en un polígono convexo (2 dimensiones) sin superposiciones. En mi problema, no puede rotar los rectángulos y puede suponer que están orientados en paralelo con los ejes. Solo se le dan las dimensiones de un...
El código de Huffman para una distribución de probabilidad ppp es el código de prefijo con la longitud de palabra de código promedio ponderada mínima ∑piℓi∑piℓi\sum p_i \ell_i , donde ℓiℓi\ell_i es la longitud de la iii ésima palabra de código. Es un teorema bien conocido que la longitud promedio...
Como sabemos, la función -clique toma un subgrafo ( abarcando ) de un gráfico -vertex completo , y genera sif contiene una -clique . Las variables en este caso corresponden a los bordes de . Se sabe (Razborov, Alon-Boppana) que, para , esta función requiere circuitos monótonos de tamaño...
Se le da un gráfico con vértices. Puede ser bipartito si quieres. Hay conjuntos de aristas (digamos disjunto). Estoy interesado en el problema de encontrar un subconjunto , lo más pequeño posible (o incluso más pequeño), de modo que el gráfico inducido tenga al menos un borde de cada clase , para...
Mi hijo de 8 años se ha aburrido creando laberintos convencionales y ha comenzado a crear variantes que se parecen a esto: La idea es comenzar desde x y alcanzar o a través de las reglas normales. Además, puede "saltar" de cualquier número entero a cualquier otro número entero , pero usted debe...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Considere este problema: dada una lista de conjuntos finitos, busque un orden s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots que minimice |s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+...|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots . ¿Hay algoritmos conocidos para esto? ¿Cuál es su...
Sabemos que los programas lineales (LP) se pueden resolver exactamente en tiempo polinómico usando el método elipsoide o un método de punto interior como el algoritmo de Karmarkar. Algunos LP con un número de variables / restricciones súper polinomiales (exponenciales) también se pueden resolver en...
Hace muchos años escuché que calcular el mínimo NFA (autómata finito no determinista) de un DFA (determinista) era una pregunta abierta, en oposición a la dirección inversa que se conoce desde hace décadas y está bien investigada con un eficiente ( n lg n ) algoritmo. ¿Alguien ha ideado un...
Considere el siguiente problema: Entrada : un hiperplano , dado por un vector y en representación binaria estándar.a ∈ Z n b ∈ ZH={y∈Rn:aTy=b}H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}a∈Zna∈Zn\mathbf{a} \in \mathbb{Z}^nb∈Zb∈Zb \in \mathbb{Z} Salida...
Hace un tiempo hice esta pregunta sobre Stack Overflow: Problema: la venta de Bob . Alguien sugirió publicar la pregunta aquí también. Alguien ya ha hecho una pregunta relacionada con este problema aquí: peso mínimo por debajo del bosque de la cardinalidad dada , pero, por lo que entiendo, no me...
Considere el espacio dimensional , y deje que sea una restricción lineal de la forma , donde , y .{ 0 , 1 } n c a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k a i ∈ R x i ∈ { 0 , 1 } k ∈ Rnnn{0,1}n{0,1}n\{0,1\}^ncccun1X1+ a2X2+ a3X3+ . . . + a n - 1Xn - 1+ anorteXnorte≥...
Recientemente me interesé en el problema general de optimizar el uso de la memoria en una situación en la que hay más de un tipo de memoria disponible, y existe una compensación entre la capacidad de un segmento de memoria dado y la velocidad de acceso a él. El ejemplo familiar es un programa que...
Estoy preparando material del curso sobre heurística para la optimización, y he estado buscando métodos de descenso coordinado. La configuración es aquí una función multivariada fff que desea optimizar. fff tiene la propiedad que se restringe a cualquier variable individual, es fácil de optimizar....
Sabemos que si la brecha entre los valores de un programa entero y su dual (la "brecha de dualidad") es cero, entonces las relajaciones de programación lineal del programa entero y la dual de la relajación, ambos admiten soluciones integrales (integralidad "cero" brecha"). Quiero saber si lo...