91 artículos
Este artículo establece una dicotomía de complejidad para el problema de reconfiguración de conjuntos dominantes a distancia , demostrando que es resoluble en tiempo polinómico en grafos divididos para y diseñando un algoritmo lineal en árboles, mientras que se mantiene como completo para PSPACE en grafos planares de grado máximo tres y en grafos bipartitos o cordales.
Este trabajo presenta un nuevo algoritmo de muestreo aleatorio con reemplazo para flujos de datos que permite obtener en una sola pasada una muestra ponderada representativa del conjunto visto hasta el momento, garantizando su corrección y eficiencia mediante pruebas formales y análisis experimental.
Esta carta presenta un método novedoso que utiliza acumuladores en cascada para calcular eficientemente sumas ponderadas con potencias de índices temporales en tiempo real, eliminando la necesidad de almacenar bloques de datos completos y reduciendo drásticamente el costo computacional de multiplicaciones.
Este artículo estudia la complejidad parametrizada del problema del camino más corto con restricciones disyuntivas positivas, estableciendo la NP-completitud de su versión clásica y presentando resultados de kernelización y tractabilidad parametrizada fija para diferentes parámetros estructurales y de tamaño de solución.
Este artículo presenta el diseño, análisis y rendimiento de una lista saltatoria determinista concurrente en nodos NUMA de muchos núcleos, evaluando además implementaciones de colas y tablas hash concurrentes frente a la biblioteca TBB de Intel, e introduciendo estrategias de gestión de memoria y uso jerárquico de estructuras de datos para reducir las latencias y los fallos de página.
Este artículo demuestra que el problema de Máximo List H-Coloreo Parcial es resoluble en tiempo polinómico en grafos libres de para cualquier grafo fijo , resolviendo así una cuestión abierta y mejorando algoritmos previos.
Este artículo presenta un marco de Propuesta-Prueba-Liberación (PTR) eficiente y diferencialmente privado para estimar el componente principal de redes, el cual logra una precisión superior y una reducción de 180 veces en el tiempo de ejecución en comparación con métodos existentes, permitiendo además la primera solución privada para el problema del subgrafo más denso.
Este trabajo presenta un nuevo marco teórico basado en una formulación matricial para derivar cotas superiores e inferiores del problema de flujo de trabajo de permutación, logrando mejoras significativas en las cotas de la mayoría de las instancias de los conjuntos de datos Taillard y VRF, además de aportar avances teóricos sobre la calidad de las cotas inferiores y la relación de aproximación asintótica.
Este artículo presenta algoritmos clásicos eficientes para los problemas y de Solución Entera Constrained, demostrando que no existe una ventaja cuántica exponencial sobre los métodos clásicos, lo que invalida el hallazgo previo de Chen, Liu y Zhandry.
Este artículo presenta un algoritmo híbrido de programación dinámica que resuelve el problema de dimensionamiento de lotes con un descuento por cantidad de un solo punto de quiebre y precios no crecientes en un tiempo de , mejorando la complejidad anterior de .
Este artículo propone un nuevo enfoque algebraico para el Problema de Reconfiguración de Satisfacción de Restricciones (RCSP) que utiliza operaciones parciales para generalizar resultados de complejidad desde dominios booleanos a entornos más amplios, ofreciendo una alternativa a los métodos topológicos tradicionales.
Este artículo presenta los primeros algoritmos de aproximación para dos generalizaciones naturales del problema de asignación cuadrática máxima (MaxQAP): una versión con restricciones de listas que logra una aproximación de y un problema de emparejamiento -cuadrático que alcanza una aproximación de , ambos basados en relajaciones de programación lineal y técnicas de redondeo aleatorio.
Este artículo demuestra que el problema de flujo de trabajo de permutación robusto bajo incertidumbre presupuestada puede resolverse mediante la resolución de un número polinómico de instancias del problema nominal, lo que permite su solución exacta en tiempo polinómico para dos máquinas y su aproximación para un número fijo de máquinas.
Este trabajo presenta algoritmos óptimos para probar la independencia de distribuciones que, mediante el uso de información predictiva auxiliar, mantienen la validez en el peor de los casos mientras mejoran significativamente la eficiencia de la muestra cuando las predicciones son precisas.
Este trabajo aborda la generalización de la selección justa de los mejores candidatos a múltiples grupos protegidos y la minimización de la disparidad respecto a una función de referencia, demostrando la complejidad computacional del problema pero proponiendo una solución eficiente y robusta para casos con pocos grupos y valores pequeños de , que incluye una nueva medida de pérdida de utilidad y valida su eficacia mediante experimentos en conjuntos de datos reales.
Este artículo presenta la implementación y simulación de algoritmos cuánticos basados en la búsqueda de Grover para resolver el problema de coordinación de señales de red (NSC) y su variante robusta, logrando una aceleración cuadrática incluso cuando la precisión de robustez decae polinomialmente con el tamaño de la red.
Este artículo generaliza el modelo de escalado de discos para grafos permitiendo que los radios se elijan dentro de un intervalo, estableciendo su complejidad paramétrica (XP, FPT o W[1]-duro) para diversas clases de grafos y resolviendo preguntas abiertas sobre grafos de clúster y completos.
Este trabajo presenta decodificadores basados en emparejamiento de grafos para códigos cuánticos topológicos bidimensionales invariantes traslacionalmente, demostrando que logran umbrales de capacidad no nulos y un rendimiento comparable a métodos más complejos al mapear las excitaciones de estos códigos a las del código torico.
Este artículo presenta un algoritmo de tiempo $2^{O(k \log k)} nk$, y demuestra que esta dependencia es óptima bajo la Hipótesis del Tiempo Exponencial (ETH).
Este artículo demuestra que calcular el camino más corto hacia la solución óptima en un politopo simple y determinar su diámetro son problemas NP-duros, resolviendo así dos preguntas abiertas de larga data, mientras que también presenta una formulación extendida que permite encontrar caminos lineales entre vértices en tiempo polinomial.