{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:16:50Z","timestamp":1742937410234,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030970987"},{"type":"electronic","value":"9783030970994"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-030-97099-4_3","type":"book-chapter","created":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T11:03:15Z","timestamp":1646218995000},"page":"37-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Algorithms for\u00a0$$k\\text {-}\\textsc {Subset}\\,\\textsc {Sum}$$ and\u00a0Variations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1368-6334","authenticated-orcid":false,"given":"Antonis","family":"Antonopoulos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6220-3722","authenticated-orcid":false,"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7825-2839","authenticated-orcid":false,"given":"Stavros","family":"Petsalakis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6505-2977","authenticated-orcid":false,"given":"Manolis","family":"Vasilakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,3]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Aumann, Y., Lewenstein, M., Lewenstein, N., Tsur, D.: Finding witnesses by peeling. ACM Trans. Algorithms 7(2) (2011). https:\/\/doi.org\/10.1145\/1921659.1921670","DOI":"10.1145\/1921659.1921670"},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/jcss.2001.1784","volume":"64","author":"C Bazgan","year":"2002","unstructured":"Bazgan, C., Santha, M., Tuza, Z.: Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem. J. Comput. Syst. Sci. 64(2), 160\u2013170 (2002). https:\/\/doi.org\/10.1006\/jcss.2001.1784","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR3","volume-title":"Dynamic Programming","author":"RE Bellman","year":"1957","unstructured":"Bellman, R.E.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1073\u20131084. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.69","DOI":"10.1137\/1.9781611974782.69"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Nakos, V.: Top-$$k$$-convolution and the quest for near-linear output-sensitive subset sum. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 982\u2013995. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384308","DOI":"10.1145\/3357713.3384308"},{"issue":"3\u20134","key":"3_CR6","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0020-0190(00)00010-7","volume":"73","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: A PTAS for the multiple subset sum problem with different knapsack capacities. Inf. Process. Lett. 73(3\u20134), 111\u2013118 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00010-7","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1022584312032","volume":"9","author":"A Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: A 3\/4-approximation algorithm for multiple subset sum. J. Heuristics 9(2), 99\u2013111 (2003). https:\/\/doi.org\/10.1023\/A:1022584312032","journal-title":"J. Heuristics"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-540-24698-5_42","volume-title":"LATIN 2004: Theoretical Informatics","author":"M Cieliebak","year":"2004","unstructured":"Cieliebak, M., Eidenbenz, S.: Measurement errors make the partial digest problem NP-hard. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 379\u2013390. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_42"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-540-45077-1_10","volume-title":"Fundamentals of Computation Theory","author":"M Cieliebak","year":"2003","unstructured":"Cieliebak, M., Eidenbenz, S., Pagourtzis, A.: Composing equipotent teams. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 98\u2013108. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45077-1_10"},{"issue":"3","key":"3_CR10","first-page":"151","volume":"14","author":"M Cieliebak","year":"2008","unstructured":"Cieliebak, M., Eidenbenz, S.J., Pagourtzis, A., Schlude, K.: On the complexity of variations of equal sum subsets. Nord. J. Comput. 14(3), 151\u2013172 (2008)","journal-title":"Nord. J. Comput."},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-540-39763-2_9","volume-title":"Algorithms in Bioinformatics","author":"M Cieliebak","year":"2003","unstructured":"Cieliebak, M., Eidenbenz, S., Penna, P.: Noisy data make the partial digest problem NP-hard. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS, vol. 2812, pp. 111\u2013123. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39763-2_9"},{"key":"3_CR12","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1016\/j.ejor.2018.10.043","volume":"274","author":"M Dell\u2019Amico","year":"2019","unstructured":"Dell\u2019Amico, M., Delorme, M., Iori, M., Martello, S.: Mathematical models and decomposition methods for the multiple knapsack problem. Eur. J. Oper. Res. 274(3), 886\u2013899 (2019). https:\/\/doi.org\/10.1016\/j.ejor.2018.10.043","journal-title":"Eur. J. Oper. Res."},{"key":"3_CR14","doi-asserted-by":"publisher","unstructured":"Jin, C., Wu, H.: A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In: 2nd Symposium on Simplicity in Algorithms (SOSA 2019), vol. 69, pp. 17:1\u201317:6 (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.17","DOI":"10.4230\/OASIcs.SOSA.2019.17"},{"key":"3_CR15","unstructured":"Khan, M.A.: Some problems on graphs and arrangements of convex bodies (2017). https:\/\/doi.org\/10.11575\/PRISM\/10182"},{"key":"3_CR16","doi-asserted-by":"publisher","unstructured":"Koiliaris, K., Xu, C.: Faster pseudopolynomial time algorithms for subset sum. ACM Trans. Algorithms 15(3) (2019). https:\/\/doi.org\/10.1145\/3329863","DOI":"10.1145\/3329863"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.cie.2019.01.010","volume":"129","author":"R Lahyani","year":"2019","unstructured":"Lahyani, R., Chebil, K., Khemakhem, M., Coelho, L.C.: Matheuristics for solving the multiple knapsack problem with setup. Comput. Ind. Eng. 129, 76\u201389 (2019). https:\/\/doi.org\/10.1016\/j.cie.2019.01.010","journal-title":"Comput. Ind. Eng."},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), pp. 125\u2013131. ACM (2004). https:\/\/doi.org\/10.1145\/988772.988792","DOI":"10.1145\/988772.988792"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/978-3-319-94776-1_50","volume-title":"Computing and Combinatorics","author":"N Melissinos","year":"2018","unstructured":"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\u2013614. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94776-1_50"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Mucha, M., Nederlof, J., Pawlewicz, J., Wegrzycki, K.: Equal-subset-sum faster than the meet-in-the-middle. In: 27th Annual European Symposium on Algorithms, ESA 2019. LIPIcs, vol. 144, pp. 73:1\u201373:16 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.73","DOI":"10.4230\/LIPIcs.ESA.2019.73"},{"issue":"19\u201321","key":"3_CR21","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.ipl.2013.07.009","volume":"113","author":"D Nanongkai","year":"2013","unstructured":"Nanongkai, D.: Simple FPTAS for the subset-sums ratio problem. Inf. Process. Lett. 113(19\u201321), 750\u2013753 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2013.07.009","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"3_CR22","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80063-7","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1999.1034","volume":"33","author":"D Pisinger","year":"1999","unstructured":"Pisinger, D.: Linear time algorithms for knapsack problems with bounded weights. J. Algorithms 33(1), 1\u201314 (1999). https:\/\/doi.org\/10.1006\/jagm.1999.1034","journal-title":"J. Algorithms"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"921","DOI":"10.12988\/ces.2017.79101","volume":"10","author":"N Voloch","year":"2017","unstructured":"Voloch, N.: MSSP for 2-D sets with unknown parameters and a cryptographic application. Contemp. Eng. Sci. 10, 921\u2013931 (2017). https:\/\/doi.org\/10.12988\/ces.2017.79101","journal-title":"Contemp. Eng. Sci."},{"issue":"6","key":"3_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(92)90226-L","volume":"42","author":"GJ Woeginger","year":"1992","unstructured":"Woeginger, G.J., Yu, Z.: On the equal-subset-sum problem. Inf. Process. Lett. 42(6), 299\u2013302 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90226-L","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-97099-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T11:03:40Z","timestamp":1646219020000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-97099-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030970987","9783030970994"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-97099-4_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"3 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/econcs.pku.edu.cn\/ijtcs2021\/CFP_G.htm","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyCHair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"56% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}