48 artículos
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 artículo introduce el marco general de los juegos "s-of-k" para posicionar juegos de puntuación donde los jugadores ganan puntos al reclamar al menos *s* elementos de un conjunto ganador, analizando tanto la puntuación óptima como la restringida a estrategias de emparejamiento en diversas cuadrículas regulares.
Este artículo inicia el estudio de los grafos mínimamente duros en la clase de los grafos débilmente cordales, proporcionando clasificaciones completas para varias subclases y ofreciendo demostraciones simplificadas de resultados previos sobre el tema.
Este artículo investiga las propiedades estructurales de las secuencias de volteos más cortas entre árboles planos en posición convexa, confirmando la validez de ciertas conjeturas en casos específicos pero refutándolas en el escenario general.
Este artículo presenta un método algebraico que permite caracterizar y sintetizar en tiempo constante las reglas de los autómatas celulares de primer grado reversibles sobre para cualquier tamaño de red, verificando únicamente tres condiciones sobre sus parámetros.
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 trabajo presenta el primer algoritmo que mejora multiplicativamente la relación de aproximación del algoritmo voraz para la maximización submodular bajo la intersección de restricciones de matroide, logrando una razón de aproximación de mediante un enfoque híbrido de búsqueda local independiente del valor de .