Scholarlink

<p>We revisit the computational problem of partitioning indivisibles into bundles among alternatives to maximize value&#xa0;(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 <Emphasis FontCategory="SansSerif">NP</Emphasis>-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&#xa0;(mixed) welfare, offering efficient approximation and non-trivial exponential-time algorithms for many hard cases.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Concise representations and complexity results for welfare-maximizing combinatorial assignment

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月27日

查看全文
  • Fredrik Präntare,
  • Leif Eriksson,
  • George Osipov,
  • Fredrik Heintz,
  • Peter Jonsson

摘要

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.