Document Open Access Logo

Group Activity Selection with Few Agent Types

Authors Robert Ganian, Sebastian Ordyniak, C. S. Rahul

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.48.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Robert Ganian
  • TU Wien, Vienna, Austria
Sebastian Ordyniak
  • University of Sheffield, Sheffield, UK
C. S. Rahul
  • University of Warsaw, Warsaw, Poland

Acknowledgements

Robert Ganian acknowledges support by the Austrian Science Fund (FWF, Project P31336), and is also affiliated with FI MUNI, Czech Republic.

Cite AsGet BibTex

Robert Ganian, Sebastian Ordyniak, and C. S. Rahul. Group Activity Selection with Few Agent Types. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.48

Abstract

The Group Activity Selection Problem (GASP) models situations where a group of agents needs to be distributed to a set of activities while taking into account preferences of the agents w.r.t. individual activities and activity sizes. The problem, along with its well-known variants sGASP and gGASP, has previously been studied in the parameterized complexity setting with various parameterizations, such as number of agents, number of activities and solution size. However, the complexity of the problem parameterized by the number of types of agents, a natural parameter proposed already in the first paper that introduced GASP, has so far remained unexplored. In this paper we establish the complexity map for GASP, sGASP and gGASP when the number of types of agents is the parameter. Our positive results, consisting of one fixed-parameter algorithm and one XP algorithm, rely on a combination of novel Subset Sum machinery (which may be of general interest) and identifying certain compression steps which allow us to focus on solutions which are "acyclic". These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta, Roy, Saurabh and Zehavi (2017). In this direction, the techniques used to establish W[1]-hardness of sGASP are of particular interest: as an intermediate step, we use Sidon sequences to show the W[1]-hardness of a highly restricted variant of multi-dimensional Subset Sum, which may find applications in other settings as well.

Subject Classification

ACM Subject Classification
  • Theory of computation → Exact and approximate computation of equilibria
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • group activity selection problem
  • parameterized complexity analysis
  • multi-agent systems

Metrics

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

Related Versions

References

  1. Martin Aigner and Günter M. Ziegler. Proofs from the Book (3. ed.). Springer, 2004. Google Scholar
  2. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  3. Andreas Darmann. Group Activity Selection from Ordinal Preferences. In Toby Walsh, editor, Algorithmic Decision Theory - 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings, volume 9346 of Lecture Notes in Computer Science, pages 35-51. Springer, 2015. Google Scholar
  4. Andreas Darmann, Janosch Döcker, Britta Dorn, Jérôme Lang, and Sebastian Schneckenburger. On Simplified Group Activity Selection. In Jörg Rothe, editor, Algorithmic Decision Theory - 5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25-27, 2017, Proceedings, volume 10576 of Lecture Notes in Computer Science, pages 255-269. Springer, 2017. Google Scholar
  5. Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, and Gerhard Woeginger. Group activity selection problem with approval preferences. International J. of Game Theory, pages 1-30, 2017. Google Scholar
  6. Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, and Gerhard J. Woeginger. Group Activity Selection Problem. In Internet and Network Economics - 8th International Workshop, WINE 2012, volume 7695 of Lecture Notes in Computer Science, pages 156-169. Springer, 2012. Google Scholar
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer Verlag, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  9. Eduard Eiben, Robert Ganian, and Sebastian Ordyniak. A Structural Approach to Activity Selection. In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden., pages 203-209. ijcai.org, 2018. Google Scholar
  10. Paul Erdős and Paul Turán. On a problem of Sidon in additive number theory, and on some related problems. Journal of the London Mathematical Society, 1(4):212-215, 1941. Google Scholar
  11. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings, pages 294-305, 2008. Google Scholar
  12. Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 33:1-33:14, 2018. Google Scholar
  13. Robert Ganian, Sebastian Ordyniak, and Ramanujan Sridharan. On Structural Parameterizations of the Edge Disjoint Paths Problem. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, volume 92 of LIPIcs, pages 36:1-36:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  14. Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Group Activity Selection on Graphs: Parameterized Analysis. In Vittorio Bilò and Michele Flammini, editors, Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings, volume 10504 of Lecture Notes in Computer Science, pages 106-118. Springer, 2017. Google Scholar
  15. Ayumi Igarashi, Robert Bredereck, and Edith Elkind. On Parameterized Complexity of Group Activity Selection Problems on Social Networks. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, pages 1575-1577. International Foundation for Autonomous Agents and Multiagent Systems, 2017. Google Scholar
  16. Ayumi Igarashi, Robert Bredereck, and Edith Elkind. On Parameterized Complexity of Group Activity Selection Problems on Social Networks. CoRR, abs/1703.01121, 2017. URL: http://arxiv.org/abs/1703.01121.
  17. Ayumi Igarashi, Robert Bredereck, Dominik Peters, and Edith Elkind. Group Activity Selection on Social Networks. CoRR, abs/1712.02712, 2017. URL: http://arxiv.org/abs/1712.02712.
  18. Ayumi Igarashi, Dominik Peters, and Edith Elkind. Group Activity Selection on Social Networks. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 565-571. AAAI Press, 2017. Google Scholar
  19. Hooyeon Lee and Virginia Vassilevska Williams. Parameterized Complexity of Group Activity Selection. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, pages 353-361. ACM, 2017. Google Scholar
  20. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. of Computer and System Sciences, 67(4):757-771, 2003. 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