Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F25%3A00378603" target="_blank" >RIV/68407700:21240/25:00378603 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1609/aaai.v39i13.33514" target="_blank" >https://doi.org/10.1609/aaai.v39i13.33514</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/aaai.v39i13.33514" target="_blank" >10.1609/aaai.v39i13.33514</a>

Result language

angličtina

Original language name

Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size

Original language description

Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied 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 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 vertex cover number).

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotics and advanced industrial production</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 39th AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-897-8

ISSN

2159-5399

e-ISSN

2374-3468

Number of pages

9

Pages from-to

13847-13855

Publisher name

AAAI Press

Place of publication

Menlo Park

Event location

Philadelphia

Event date

Feb 27, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001477539600041