Group Activity Selection with Few Agent Types
Tóm tắt
In this paper we establish the complexity map for the Group Activity Selection Problem (GASP), along with two of its prominent variants called sGASP and gGASP, focusing on the case when the number of types of agents is the parameter. In all these problems, one is given a set of agents (each with their own preferences) and a set of activities, and the aim is to assign agents to activities in a way which satisfies certain global as well as preference-based conditions. 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 that allow us to focus on solutions with a simpler, well-defined structure (in particular, they are “acyclic”). These algorithms are complemented by matching lower bounds, which among others close a gap to a recently obtained tractability result of Gupta et al. (in: Algorithmic game theory—10th international symposium, SAGT 2017, vol 10504 of lecture notes in computer science, Springer, 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.
Tài liệu tham khảo
Aigner, M., Ziegler, G.M.: Proofs from the Book, 3rd edn. Springer, New York (2004)
Ballester, C.: Np-completeness in hedonic games. Games Econom. Behav. 49(1), 1–30 (2004)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015)
Darmann, A.: Group activity selection from ordinal preferences. In: Algorithmic Decision Theory—4th International Conference, ADT 2015, volume 9346 of Lecture Notes in Computer Science, pp. 35–51. Springer (2015)
Darmann, A., Döcker, J., Dorn, B., Lang, J., Schneckenburger, S.: On simplified group activity selection. In Algorithmic Decision Theory—5th International Conference, ADT 2017, volume 10576 of Lecture Notes in Computer Science, pp. 255–269. Springer (2017)
Darmann, A., Elkind, E., Kurz, S., Lang, J., Schauer, J., Woeginger, G.: Group activity selection problem with approval preferences. Int. J. Game Theory 47, 767–796 (2018)
Darmann, A., Elkind, E., Kurz, S., Lang, J., Schauer, J., Woeginger, G.J: Group activity selection problem. In: Internet and Network Economics—8th International Workshop, WINE 2012, volume 7695 of Lecture Notes in Computer Science, pp. 156–169. Springer (2012)
Diestel, R.: Graph Theory, volume 173 of Graduate Texts in Mathematics, 4th edn. Springer, New York (2012)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, New York (2013)
Eiben, E., Ganian, R., Ordyniak, S.: A structural approach to activity selection. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, pp. 203–209. ijcai.org (2018)
Erdős, P., Turán, P.: On a problem of Sidon in additive number theory, and on some related problems. J. Lond. Math. Soc. 1(4), 212–215 (1941)
Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Algorithms and Computation, 19th International Symposium, ISAAC 2008, pp. 294–305 (2008)
Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica 83(1), 297–336 (2021)
Ganian, R., Ordyniak, S., Ramanujan, M.S.: On structural parameterizations of the edge disjoint paths problem. Algorithmica 83(6), 1605–1637 (2021)
Garey, M.R., Johnson, D.R.: Computers and Intractability. W. H. Freeman and Company, New York (1979)
Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: Group activity selection on graphs: parameterized analysis. In: Algorithmic Game Theory—10th International Symposium, SAGT 2017, volume 10504 of Lecture Notes in Computer Science, pp. 106–118. Springer (2017)
Igarashi, A., Bredereck, R., Elkind, E.: 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, pp. 1575–1577. International Foundation for Autonomous Agents and Multiagent Systems (2017)
Igarashi, A., Bredereck, R., Elkind, E.: On parameterized complexity of group activity selection problems on social networks. CoRR, arXiv:1703.01121 (2017)
Igarashi, A., Bredereck, R., Peters, D., Elkind, E.: Group activity selection on social networks. CoRR, arXiv:1712.02712 (2017)
Igarashi, A., Peters, D., Elkind, E.: Group activity selection on social networks. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 565–571. AAAI Press (2017)
Lee, H., Williams, V.V.: Parameterized complexity of group activity selection. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, pp. 353–361. ACM (2017)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)