dc.contributor.author | Baste, Julien | |
dc.contributor.author | Fellows, Michael Ralph | |
dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Masařík, Tomáš | |
dc.contributor.author | Oliveira, Mateus De Oliveira | |
dc.contributor.author | Philip, Geevarghese | |
dc.contributor.author | Rosamond, Frances | |
dc.date.accessioned | 2023-01-04T13:29:57Z | |
dc.date.available | 2023-01-04T13:29:57Z | |
dc.date.created | 2022-05-06T14:17:36Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 0004-3702 | |
dc.identifier.uri | https://hdl.handle.net/11250/3040978 | |
dc.description.abstract | 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. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present 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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/deed.no | * |
dc.title | Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright 2022 Elsevier | en_US |
dc.source.articlenumber | 103644 | en_US |
cristin.ispublished | true | |
cristin.fulltext | postprint | |
cristin.qualitycode | 2 | |
dc.identifier.doi | 10.1016/j.artint.2021.103644 | |
dc.identifier.cristin | 2022172 | |
dc.source.journal | Artificial Intelligence | en_US |
dc.relation.project | Norges forskningsråd: 326537 | en_US |
dc.relation.project | Norges forskningsråd: 288761 | en_US |
dc.identifier.citation | Artificial Intelligence. 2022, 303, 103644. | en_US |
dc.source.volume | 303 | en_US |