Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.28
URN: urn:nbn:de:0030-drops-155391
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15539/
Lokshtanov, Daniel ; Saurabh, Saket ; Suri, Subhash ; Xue, Jie
An ETH-Tight Algorithm for Multi-Team Formation
| pdf-format: |
|
Abstract
In the Multi-Team Formation problem, we are given a ground set C of n candidates, each of which is characterized by a d-dimensional attribute vector in ℝ^d, and two positive integers α and β satisfying α β ≤ n. The goal is to form α disjoint teams T₁,...,T_α ⊆ C, each of which consists of β candidates in C, such that the total score of the teams is maximized, where the score of a team T is the sum of the h_j maximum values of the j-th attributes of the candidates in T, for all j ∈ {1,...,d}. Our main result is an 2^{2^O(d)} n^O(1)-time algorithm for Multi-Team Formation. This bound is ETH-tight since a 2^{2^{d/c}} n^O(1)-time algorithm for any constant c > 12 can be shown to violate the Exponential Time Hypothesis (ETH). Our algorithm runs in polynomial time for all dimensions up to d = clog log n for a sufficiently small constant c > 0. Prior to our work, the existence of a polynomial time algorithm was an open problem even for d = 3.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs.FSTTCS.2021.28,
author = {Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
title = {{An ETH-Tight Algorithm for Multi-Team Formation}},
booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages = {28:1--28:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-215-0},
ISSN = {1868-8969},
year = {2021},
volume = {213},
editor = {Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15539},
URN = {urn:nbn:de:0030-drops-155391},
doi = {10.4230/LIPIcs.FSTTCS.2021.28},
annote = {Keywords: Team formation, Parameterized algorithms, Exponential Time Hypothesis}
}
| Keywords: | Team formation, Parameterized algorithms, Exponential Time Hypothesis | |
| Seminar: | 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 29.11.2021 |
