Mochila 0-1 em Tempo Quase Quadrático

Estudamos algoritmos de tempo pseudo-polynomial para o problema fundamental da Mochila 0-1. O recente interesse em pesquisa tem se concentrado em sua complexidade fina em relação ao número de itens n e ao peso máximo do item wmax. Sob a hipótese de convolução (min,+), a Mochila 0-1 não possui algoritmos de tempo O((n+wmax)²−δ) (Cygan-Mucha-Węgrzycki-Włodarczyk 2017 e K'unnemann-Paturi-Schneider 2017). No lado do limite superior, atualmente o algoritmo mais rápido roda em Õ(n + 12/5) tempo (Chen, Lian, Mao, e Zhang 2023), melhorando o algoritmo anterior de tempo O(n + wmax³) de Polak, Rohwedder, e Węgrzycki (2021).