Document Open Access Logo

An ETH-Tight Algorithm for Multi-Team Formation

Authors Daniel Lokshtanov, Saket Saurabh, Subhash Suri, Jie Xue

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.28.pdf
  • Filesize: 0.67 MB
  • 9 pages

Document Identifiers

Author Details

Daniel Lokshtanov
  • University of California, Santa Barbara, CA, USA
Saket Saurabh
  • The Institute of Mathematical Sciences (HBNI), Chennai, India
  • University of Bergen, Norway
Subhash Suri
  • University of California, Santa Barbara, CA, USA
Jie Xue
  • New York University Shanghai, China

Acknowledgements

We would like to thank an anonymous reviewer for pointing us to the statement of [Kouteckỳ et al., 2018], allowing us to drastically simplify a previous version of the paper.

Cite AsGet BibTex

Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue. An ETH-Tight Algorithm for Multi-Team Formation. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 28:1-28:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.28

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Team formation
  • Parameterized algorithms
  • Exponential Time Hypothesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nikhil Bansal, Tim Oosterwijk, Tjark Vredeveld, and Ruben Van Der Zwaan. Approximating vector scheduling: almost matching upper and lower bounds. Algorithmica, 76(4):1077-1096, 2016. Google Scholar
  2. Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM J. Comput., 45(1):67-83, 2016. Google Scholar
  3. Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Kouteckỳ, Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.01361.
  4. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. Google Scholar
  5. Erin L. Fitzpatrick and Ronald G. Askin. Forming effective worker teams with multi-functional skill requirements. Computers & Industrial Engineering, 48(3):593-608, 2005. Google Scholar
  6. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming, 137(1-2):325-341, 2013. Google Scholar
  7. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  8. Jon Kleinberg and Maithra Raghu. Team performance with test scores. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, pages 511-528, 2015. Google Scholar
  9. Dušan Knop and Martin Kouteckỳ. Scheduling meets n-fold integer programming. Journal of Scheduling, 21(5):493-503, 2018. Google Scholar
  10. Martin Kouteckỳ, Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  11. Theodoros Lappas, Kun Liu, and Evimaria Terzi. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, pages 467-476, 2009. Google Scholar
  12. Patrick R. Laughlin and Andrea B. Hollingshead. A theory of collective induction. Organizational Behavior and Human Decision Processes, 61(1):94-107, 1995. Google Scholar
  13. Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research, 35(4):795-806, 2010. Google Scholar
  14. Tomasz P. Michalak, Talal Rahwan, Edith Elkind, Michael J. Wooldridge, and Nicholas R. Jennings. A hybrid exact algorithm for complete set partitioning. Artif. Intell., 230:14-50, 2016. Google Scholar
  15. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Math. Program., 14(1):265-294, 1978. Google Scholar
  16. Scott Page. The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, and Societies. Princeton University Press, 2007. Google Scholar
  17. Marcin Pilipczuk and Manuel Sorge. A double exponential lower bound for the distinct vectors problem. CoRR, abs/2002.01293, 2020. URL: http://arxiv.org/abs/2002.01293.
  18. Habibur Rahman, Senjuti Basu Roy, Saravanan Thirumuruganathan, Sihem Amer-Yahia, and Gautam Das. Optimized group formation for solving collaborative tasks. The VLDB Journal, 28(1):1-23, February 2019. Google Scholar
  19. Talal Rahwan, Tomasz P. Michalak, Michael J. Wooldridge, and Nicholas R. Jennings. Coalition structure generation: A survey. Artif. Intell., 229:139-174, 2015. Google Scholar
  20. Thomas Schibler, Ambuj Singh, and Subhash Suri. On multi-dimensional team formation. In Proc. of the 31st Canadian Conference on Computational Geometry, pages 146-152, 2019. Google Scholar
  21. Travis C. Service and Julie A. Adams. Coalition formation for task allocation: theory and algorithms. Autonomous Agents and Multi-Agent Systems, 22(2):225-248, March 2011. Google Scholar
  22. Marjorie E. Shaw. A comparison of individuals and small groups in the rational solution of complex problems. The American Journal of Psychology, 44(3):491-504, 1932. Google Scholar
  23. Onn Shehory and Sarit Kraus. Methods for task allocation via agent coalition formation. Artif. Intell., 101(1-2):165-200, 1998. Google Scholar
  24. I. D. Steiner. Group process and productivity. New York: Academic Press, 1972. Google Scholar
  25. Xinyu Wang, Zhou Zhao, and Wilfred Ng. A comparative study of team formation in social networks. In Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, pages 389-404. Springer, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact