Se necesita una referencia a las técnicas para demostrar que el tamaño de una brecha de integralidad está limitado por alguna expresión para un LP particular (o SDP, pero menos importante). También sería bueno tener una referencia a un lugar donde se describan técnicas para minimizar las brechas de...
Considere los siguientes dos algoritmos para buscar en una matriz ordenada de nnn elementos: A) búsqueda de interpolación y búsqueda binaria simulada en paralelo, y B) busque a través de pasos de interpolación alternos y pasos binarios. Ambos algoritmos son de peor complejidad de caso...
Para un lenguaje libre de contexto determinado G, que llamamos un no terminal nullable si , es decir, podemos derivar la cadena vacía de después de aplicar un número finito de producciones.UNAyoAiA_i UNAyo→∗ϵAi→∗ϵA_i \rightarrow^* \epsilonUNAyoAiA_i Hay un algoritmo simple para determinar qué no...
Link-cut tree es una estructura de datos inventada por Sleator y Tarjan, que admite varias operaciones y consultas en unbosque de nodos en el tiempo O ( log n ) . (Por ejemplo, el enlace de operacióncombina dos árboles en el bosque en uno, mientras que la operación de corte divide un árbol en el...
Recientemente he leído algunas cosas sobre problemas de optimización incremental, pero no puedo ver cuál es la diferencia entre esos y los problemas de optimización en línea. Mi impresión es que puedo definir cada problema en línea como una contraparte incremental (lo contrario es claramente...
Estoy buscando trabajo para calcular el cierre transitivo de una relación afín en el siguiente sentido: Sea la relación definida por un sistema de desigualdades lineales sobre las variables reales , es decirx 1 , ... , x n , x ′ 1 , ... , x ′
Que le den un conjunto de Dirigido acíclicos gráficos G 1 , G 2 , . . . , G n sobre el mismo conjunto de vértices . También se le da una permutación del conjunto de vértices . ¿Cuál es el mejor algoritmo que podría identificar los gráficos entre que tienen como un tipo topológico? ¿Podría alguien...
Quiero dividir N números dados (pueden o no ser iguales) en 2 subconjuntos de modo que los 2 subconjuntos tengan una suma lo más cercana posible y también la cardinalidad de los conjuntos es igual (si n es par) o difiere solo en 1 ( si n es impar) Creo que podemos hacer esto en tiempo pseudo...
Dado un gráfico acíclico dirigido con nodos, ¿cómo se puede determinar si hay una ruta entre alguno de los siguientes n pares de nodos ? Hay un algoritmo simple en (donde m es el número de aristas) haciendo una búsqueda desde cada nodo , pero ¿se puede hacer mejor?2n2n2nO ( n ⋅ ( n + m ) ) 1 … n( 1...
Estoy mirando la página 28 de Lovasz "Programas semidefinidos y optimización combinatoria" y ofrece la siguiente aproximación del número de independencia del gráfico maxu′Zumaxu′Zu\max u' Z u sujeto a Z≻0Z≻0Z\succ 0 Zij=0 ∀ij∈E(G)Zij=0 ∀ij∈E(G)Z_{ij}=0 \ \forall ij\in...
Se nos dan pilas que contienen "elementos" de diferente color y una máquina que puede procesar múltiples elementos del mismo color de una sola vez. En cada paso, podemos eliminar un elemento de la parte superior de cada pila y ponerlo en nuestra máquina (de manera efectiva, la máquina puede...
Un -net para un espacio de rango es un subconjunto de tal que no es vacío para todos tal que.( X , R ) N X N ∩ R R ∈ R | X ∩ R | ≥ ε | X |εε\varepsilon( X, R )(X,R)(X,\mathcal{R})norteNNXXXnorte∩ RN∩RN\cap RR ∈ RR∈RR\in \mathcal{R}El | X∩ R | ≥ ε | XEl ||X∩R|≥ε|X||X\cap R| \ge \varepsilon |X| Dado...
Estoy planeando ejecutar un "experimento" cuando enseñe mi clase de algoritmos este otoño, con una computadora muy antigua y limitada (el factor limitante principal es probablemente la memoria, posiblemente tan bajo como 16 KB) y uno moderno / estándar. La idea es resolver un problema con un...
Tengo un DAG de dependencias que contiene muchos bordes redundantes (ver ejemplo a continuación). Quiero un algoritmo "rápido" (es decir, puede manejar un gráfico con varios miles de nodos / bordes) que encuentre un gráfico secundario mínimo. Por ejemplo: A -> B -> C A -> C en...
[Editar 21 de julio de 2011: edité la pregunta para pedir más ejemplos] Esta pregunta requiere una discusión documentada de o más ejemplos de una observación heurística. Algunos problemas matemáticos que admiten algoritmos eficientes parecen ser de naturaleza convexa. Estoy pensando en programas...
Dado un gráfico G ( V, E)G(V,E)G(V,E) , el problema clásico de coincidencia máxima es elegir el subconjunto máximo de aristas METROMETROM st, para cada arista ( u , v ) ∈ M(tu,v)∈METRO(u,v) \in M , re( u ) = d( v ) = 1re(tu)=re(v)=1d(u)=d(v)=1 . ¿Alguien ha estudiado la siguiente variante? Para...
Wikipedia afirma que las ventajas de smoothsort sobre heapsort es que a veces se acerca más al tiempo O (n). Ahora me preguntaba ¿qué ventaja tiene la ordenación dinámica sobre la ordenación suave? O para reformular esta pregunta, ¿la ordenación suave siempre es una mejor opción que la ordenación...
Teniendo en cuenta los números enteros positivos y correo , lo que se sabe sobre el espacio y el tiempo complejidad de encontrar el peso de Hamming (número de 1 binarios) de b correo ?sibbeeebebeb^e Si bits son disponibles, el número simplemente se puede calcular mediante técnicas estándar y los...
Sea , B i una secuencia de matrices circulantes de tamaño n × n .UNAyoAiA_{i}siyoBiB_{i}n × nn×nn \times n Sabemos que se puede calcular en el tiempo cuadrática (uso FFT diagonalizar y añadir las matrices diagonales y aplicar IFFT).∑ni=1AiBi∑i=1nAiBi\sum_{i=1}^{n}A_{i}B_{i} Suponiendo es una...
Existe un método trivial para simular una caminata aleatoria a través de un gráfico exponiendo una matriz de adyacencia estocástica, pero el problema se vuelve más difícil si solicita que la caminata aleatoria se evite por sí misma. En otras palabras, el proceso debe atravesar el gráfico utilizando...