Aproximación (1 − 𝜀 ) del Problema de la Mochila en Tiempo Casi Cuadrático

El problema de la mochila es uno de los problemas más fundamentales en la ciencia de la computación teórica. En el contexto de la aproximación (1 − є), aunque existe un límite inferior muy preciso de (n + 1 / є) 2 − o(1) basado en la hipótesis de convolución (min, +) (K'unnemann, Paturi y Stefan Schneider, ICALP 2017 y Cygan, Mucha, Wegrzycki y Wlodarczyk, 2017), el mejor algoritmo es aleatorio y se ejecuta en Õ(n + (1/є)11/5/2Ω(√log(1/є))) tiempo (Deng, Jin y Mao, SODA 2023), y sigue siendo un problema importante y abierto si existe un algoritmo con un tiempo de ejecución que coincida con el límite inferior (hasta un factor sub-polynomial). Respondemos a la pregunta de manera positiva al mostrar un esquema de aproximación determinista (1 − є) para el problema de la mochila que se ejecuta en Õ(n + (1 / є) 2) tiempo. Primero ampliamos un lema conocido de manera recursiva para reducir el problema a una aproximación aditiva n є para n ítems con beneficios en [1, 2). Luego, damos un algoritmo simple y eficiente basado en geometría para el problema reducido.