研究有限规模团队的最优组队方法，提出高效算法并证明其理论最优性。
Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
- 针对团队规模受限的组队问题，设计基于树宽的精确算法
- 算法在树状结构上表现良好，时间复杂度随输入增长缓慢
- 证明该算法在理论上无法被显著超越，适用于小团队场景
考虑将一组具有偏好关系的参与者划分成若干团队，要求每个团队大小不超过给定上限。本研究系统分析了这一受限组队问题的计算复杂性，给出了多个难以解决的结果，并提出多种可扩展的精确算法（FPT）。主要贡献是设计了一种针对树状结构（有界树宽）且团队规模较小的高效算法。进一步证明该算法在渐近意义下是最优的：在合理理论假设下，即使对于星型结构（有界顶点覆盖数），也不存在能显著优于该算法的通用算法。
原文摘要 · Abstract (English)
Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied \textsc{Coalition Formation} problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded \emph{treewidth}) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded \emph{vertex cover number}).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。