{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:59:14Z","timestamp":1743008354505,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030921200"},{"type":"electronic","value":"9783030921217"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-92121-7_4","type":"book-chapter","created":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T17:13:15Z","timestamp":1638983595000},"page":"40-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact Counting and\u00a0Sampling of\u00a0Optima for\u00a0the\u00a0Knapsack Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4121-4668","authenticated-orcid":false,"given":"Jakob","family":"Bossek","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,9]]},"reference":[{"issue":"1","key":"4_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jagm.1996.0851","volume":"24","author":"AZ Broder","year":"1997","unstructured":"Broder, A.Z., Mayr, E.W.: Counting minimum weight spanning trees. J. Algorithms 24(1), 171\u2013176 (1997)","journal-title":"J. Algorithms"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Cai, J.Y., Chen, X.: Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, USA, 1st edn. (2017)","DOI":"10.1017\/9781107477063"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Do, A.V., Bossek, J., Neumann, A., Neumann, F.: Evolving diverse sets of tours for the travelling salesperson problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2020, pp. 681\u2013689. ACM (2020)","DOI":"10.1145\/3377930.3389844"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Dyer, M.: Approximate counting by dynamic programming. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing. STOC 2003, pp. 693\u2013699. Association for Computing Machinery, New York, NY, USA (2003)","DOI":"10.1145\/780542.780643"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-44436-X_12","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M Dyer","year":"2000","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: On the relative complexity of approximate counting problems. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 108\u2013119. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44436-X_12"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Fichte, J.K., Hecher, M., Meier, A.: Counting complexity for reasoning in abstract argumentation. In: Proceedings of the The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, pp. 2827\u20132834. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33012827"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-319-94144-8_11","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2018","author":"JK Fichte","year":"2018","unstructured":"Fichte, J.K., Hecher, M., Morak, M., Woltran, S.: Exploiting treewidth for projected model counting and its limits. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) SAT 2018. LNCS, vol. 10929, pp. 165\u2013184. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94144-8_11"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-013-0079-3","volume":"24","author":"H Fournier","year":"2015","unstructured":"Fournier, H., Malod, G., Mengel, S.: Monomials in arithmetic circuits: complete problems in the counting hierarchy. Comput. Complex. 24(1), 1\u201330 (2015)","journal-title":"Comput. Complex."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Katz, M., Sohrabi, S.: Reshaping diverse planning. In: Proceedings of the The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 9892\u20139899. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i06.6543"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Katz, M., Sohrabi, S., Udrea, O.: Top-quality planning: finding practically useful sets of best plans. In: Proceedings of the The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 9900\u20139907. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i06.6544"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Katz, M., Sohrabi, S., Udrea, O., Winterer, D.: A novel iterative approach to top-$$k$$ planning. In: Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, ICAPS 2018, pp. 132\u2013140. AAAI Press (2018)","DOI":"10.1609\/icaps.v28i1.13893"},{"key":"4_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00224-014-9571-7","volume":"58","author":"M Mihal\u00e1k","year":"2016","unstructured":"Mihal\u00e1k, M., \u0160r\u00e1mek, R., Widmayer, P.: Approximately counting approximately-shortest paths in directed acyclic graphs. Theory Comput. Syst. 58(1), 45\u201359 (2016)","journal-title":"Theory Comput. Syst."},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Neumann, A., Gao, W., Doerr, C., Neumann, F., Wagner, M.: Discrepancy-based evolutionary diversity optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 991\u2013998 (2018)","DOI":"10.1145\/3205455.3205532"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Neumann, A., Gao, W., Wagner, M., Neumann, F.: Evolutionary diversity optimization using multi-objective indicators. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 837\u2013845 (2019)","DOI":"10.1145\/3321707.3321796"},{"issue":"4","key":"4_CR16","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1287\/opre.47.4.570","volume":"47","author":"D Pisinger","year":"1999","unstructured":"Pisinger, D.: Core problems in knapsack algorithms. Oper. Res. 47(4), 570\u2013575 (1999)","journal-title":"Oper. Res."},{"issue":"9","key":"4_CR17","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","volume":"32","author":"D Pisinger","year":"2005","unstructured":"Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271\u20132284 (2005)","journal-title":"Comput. Oper. Res."},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.ic.2019.04.001","volume":"267","author":"R Rizzi","year":"2019","unstructured":"Rizzi, R., Tomescu, A.I.: Faster FPTASes for counting and random generation of knapsack solutions. Inf. Comput. 267, 135\u2013144 (2019)","journal-title":"Inf. Comput."},{"key":"4_CR19","unstructured":"Sohrabi, S., Riabov, A.V., Udrea, O., Hassanzadeh, O.: Finding diverse high-quality plans for hypothesis generation. In: Proceedings of the 22nd European Conference on Artificial Intelligence, ECAI 2016. Frontiers in Artificial Intelligence and Applications, vol. 285, pp. 1581\u20131582. IOS Press (2016)"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Ulrich, T., Thiele, L.: Maximizing population diversity in single-objective optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 641\u2013648 (2011)","DOI":"10.1145\/2001576.2001665"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"4_CR22","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1137\/11083976X","volume":"41","author":"D \u0160tefankovi\u010d","year":"2012","unstructured":"\u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41(2), 356\u2013366 (2012)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Learning and Intelligent Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-92121-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T17:47:26Z","timestamp":1673977646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-92121-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030921200","9783030921217"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-92121-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"9 December 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LION","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Learning and Intelligent Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","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":"20 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 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":"lion2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/lion15.sba-research.org\/index.html","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":"35","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":"30","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":"86% - 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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}