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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

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

Popis výsledku anglicky

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).

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotika a pokročilá průmyslová výroba</a><br>

Návaznosti

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

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 39th AAAI Conference on Artificial Intelligence

ISBN

978-1-57735-897-8

ISSN

2159-5399

e-ISSN

2374-3468

Počet stran výsledku

9

Strana od-do

13847-13855

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

Philadelphia

Datum konání akce

27. 2. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001477539600041