Resumo Nós revisitamos o problema computacional de particionar bens indivisíveis em pacotes entre alternativas para maximizar o valor (por exemplo, bem-estar). Esses problemas têm amplas aplicações, ainda assim muitas variantes importantes são computationalmente difíceis, incluindo casos bem conhecidos em pesquisa operacional, economia computacional e inteligência artificial. Para abordar essa complexidade, analisamos restrições novas e representações concisas para essa classe de problema e estabelecemos novos resultados de complexidade. Baseando-se nessas descobertas, apresentamos limites de complexidade aprimorados usando uma caracterização baseada em hipergrafos e introduzimos um novo método de programação dinâmica "bootstrapped" que supera significativamente os algoritmos existentes para uma ampla classe de problemas. Outras descobertas incluem: solucionabilidade em tempo polinomial para problemas com sinergias não negativas e duas alternativas; o problema permanecendo NP-difícil mesmo quando limitando o tamanho dos pacotes a dois, com outros casos sendo solucionáveis em tempo polinomial; e exploração de limites para casos mais gerais permitindo externalidades e bem-estar balanceado (misto), oferecendo aproximações eficientes e algoritmos não triviais em tempo exponencial para muitos casos difíceis.
Präntare et al. (Wed,) estudaram essa questão.