{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T20:50:56Z","timestamp":1769979056481,"version":"3.49.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.<\/jats:p>","DOI":"10.24963\/ijcai.2020\/156","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T12:12:10Z","timestamp":1594210330000},"page":"1119-1125","source":"Crossref","is-referenced-by-count":5,"title":["Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory"],"prefix":"10.24963","author":[{"given":"Julien","family":"Baste","sequence":"first","affiliation":[{"name":"Ulm University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[{"name":"University of Warsaw"},{"name":"Charles University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mateus","family":"de Oliveira Oliveira","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute"},{"name":"UMI ReLaX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","theme":"Artificial Intelligence","location":"Yokohama, Japan","acronym":"IJCAI-PRICAI-2020","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2020,7,11]]},"end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T02:13:38Z","timestamp":1594260818000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/156"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/156","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}