New algorithm solves a $1 trillion problem in resource allocation
Researchers have cracked a notoriously difficult math problem that affects everything from supply chain optimization to corporate mergers. Their faster algorithm could help companies and governments save time and money when dividing assets, assigning contracts, and allocating limited resources among competing needs.
Originaltitel: Concise representations and complexity results for welfare-maximizing combinatorial assignment
<p>We revisit the computational problem of partitioning indivisibles into bundles among alternatives to maximize value (e.g., welfare). These problems have broad applications, yet many important variants are computationally hard, including well-known instances in operations research, computational economics, and artificial intelligence. To address this complexity, we analyze novel restrictions and concise representations for this problem class and establish new complexity results. Building on these findings, we present improved complexity bounds using a hypergraph-based characterization and introduce a novel "bootstrapped" dynamic programming method that significantly outperforms existing algorithms for a broad class of problems. Other findings include: polynomial-time solvability for problems with non-negative synergies and two alternatives; the problem remaining NP-hard even when bounding bundle sizes to two, with other instances being polynomial-time solvable; and exploration of bounds for more general cases allowing externalities and balanced (mixed) welfare, offering efficient approximation and non-trivial exponential-time algorithms for many hard cases.</p>