Abstract
In this paper, we study the problem of counting the number of different knapsack solutions with a prescribed cardinality. We present an FPTAS for this problem, based on dynamic programming. We also introduce two different types of semi-fair allocations of indivisible goods between two players. By semi-fair allocations, we mean allocations that ensure that at least one of the two players will be free of envy. We study the problem of counting such allocations and we provide FPTASs for both types, by employing our FPTAS for the prescribed cardinality knapsack problem.
Theofilos Triommatis was supported in part for this work by EPSRC grant EP/S023445/1 EPSRC Centre for Doctoral Training in Distributed Algorithms: the what, how and where of next-generation data science, https://gow.epsrc.ukri.org/NGBOViewGrant.aspx?GrantRef=EP/S023445/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Amanatidis, G., Birmpas, G., Markakis, V.: Comparing approximate relaxations of envy-freeness. In: Proceedings of IJCAI 2018, pp. 42–48 (2018). ijcai.org
Buhmann, J.M., Gronskiy, A., Mihalák, M., Pröger, T., Srámek, R., Widmayer, P.: Robust optimization in the presence of uncertainty: a generic approach. J. Comput. Syst. Sci. 94, 135–166 (2018)
Dyer, M.E.: Approximate counting by dynamic programming. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 693–699. ACM (2003)
Dyer, M.E., Goldberg, L.A., Greenhill, C.S., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471–500 (2004)
Foley, D.K.: Resource allocation and the public sector. Yale Econ Essays 7, 45–98 (1967)
Kiayias, A., Pagourtzis, A., Sharma, K., Zachos, S.: Acceptor-definable counting classes. In: Manolopoulos, Y., Evripidou, S., Kakas, A.C. (eds.) PCI 2001. LNCS, vol. 2563, pp. 453–463. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-38076-0_29
Li, W., Lee, J., Shroff, N.B.: A faster FPTAS for knapsack problem with cardinality constraint. CoRR, abs/1902.00919 (2019)
Melissinos, N., Pagourtzis, A.: A faster FPTAS for the subset-sums ratio problem. In: Wang, L., Zhu, D. (eds.) COCOON 2018. LNCS, vol. 10976, pp. 602–614. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94776-1_50
Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 741–752. Springer, Heidelberg (2006). https://doi.org/10.1007/11821069_64
Stefankovic, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41(2), 356–366 (2012)
Triommatis, T., Pagourtzis, A.: Approximate #knapsack computations to count semi-fair allocations. CoRR, abs/1912.12430 (2019)
Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189–201 (1979)
Yazidi, A., Jonassen, T.M., Herrera-Viedma, E.: An aggregation approach for solving the non-linear fractional equality knapsack problem. Expert Syst. Appl. 110, 323–334 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Triommatis, T., Pagourtzis, A. (2020). Approximate #Knapsack Computations to Count Semi-fair Allocations. In: Chen, J., Feng, Q., Xu, J. (eds) Theory and Applications of Models of Computation. TAMC 2020. Lecture Notes in Computer Science(), vol 12337. Springer, Cham. https://doi.org/10.1007/978-3-030-59267-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-59267-7_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59266-0
Online ISBN: 978-3-030-59267-7
eBook Packages: Computer ScienceComputer Science (R0)