Mochila con elementos pequeños en tiempo casi cuadrático

El problema de la mochila es uno de los problemas NP-completos más fundamentales en la intersección de la informática, la optimización y la investigación operativa. Una línea reciente de investigación trabajó en entender la complejidad de los algoritmos de tiempo pseudopolinómico para la mochila parametrizados por el peso máximo del ítem wmax y el número de ítems n. Un límite inferior condicional descarta que la mochila se pueda resolver en un tiempo O((n+wmax)2−δ) para cualquier δ > 0 Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17. Esto planteó la pregunta de si la mochila se puede resolver en tiempo Õ((n+wmax)2). Esto estaba abierto tanto para la mochila 0-1 (donde cada ítem puede ser recogido como máximo una vez) como para la mochila acotada (donde cada ítem viene con una multiplicidad). La búsqueda de resolver esta pregunta llevó a algoritmos que resuelven la mochila acotada en tiempo Õ(n3 wmax2) Tamir'09, Õ(n2 wmax2) y Õ(n wmax3) Bateni, Hajiaghayi, Seddighin, Stein'18, O(n2 wmax2) y Õ(n wmax2) Eisenbrand y Weismantel'18, O(n + wmax3) Polak, Rohwedder, Wegrzycki'21, y muy recientemente Õ(n + wmax12/5) Chen, Lian, Mao, Zhang'23. En este artículo resolvemos esta pregunta diseñando un algoritmo para la mochila acotada con un tiempo de ejecución Õ(n + wmax2), que es condicionalmente casi óptimo. Esto resuelve la pregunta tanto para el clásico problema de la mochila 0-1 como para el problema de la mochila acotada.