Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory

Autor: Michael R. Fellows, Frances A. Rosamond, Julien Baste, Mateus de Oliveira Oliveira, Lars Jaffke, Geevarghese Philip, Tomáš Masařík

Publikováno v: Artificial Intelligence
Artificial Intelligence, 2022, 303, pp.103644. ⟨10.1016/j.artint.2021.103644⟩
Artificial Intelligence, Elsevier, 2022, 303, pp.103644. ⟨10.1016/j.artint.2021.103644⟩
IJCAI
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}
Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence, Jul 2020, Yokohama, Japan. pp.1119-1125, ⟨10.24963/ijcai.2020/156⟩
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

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.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::adf19510b9f6c7ba32d99cbdf89ea227
https://hal.science/hal-03469328

Collaborating with Hans: Some Remaining Wonderments

Autor: Michael R. Fellows, Frances A. Rosamond

Publikováno v: Treewidth, Kernels, and Algorithms ISBN: 9783030420703
Treewidth, Kernels, and Algorithms

This paper celebrates some family adventures, three concrete open problems and several research directions that have developed over our long collaboration.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::598734aeb81d06aae029099989a0066c
https://doi.org/10.1007/978-3-030-42071-0_2

Parameterized approximation via fidelity preserving transformations

Autor: Frances A. Rosamond, Hadas Shachnai, Michael R. Fellows, Ariel Kulik

Publikováno v: Journal of Computer and System Sciences. 93:30-40

We motivate and describe a new parameterized approximation paradigm which studies the interaction between approximation ratio and running time for any parametrization of a given optimization problem. As a key tool, we introduce the concept of an α-s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::bbca28594ecb5b5306511b326fe2472b
https://doi.org/10.1016/j.jcss.2017.11.001

Tractable Parameterizations for the Minimum Linear Arrangement Problem

Autor: Hadas Shachnai, Michael R. Fellows, Danny Hermelin, Frances A. Rosamond

Publikováno v: ACM Transactions on Computation Theory. 8:1-12

The M inimum L inear A rrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, par

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ce4c52b3979c37c0a39ae6716c6d6b0b
https://doi.org/10.1145/2898352

A Survey on the Complexity of Flood-Filling Games

Autor: Frances A. Rosamond, Maise Dantas da Silva, Uéverton S. Souza, Michael R. Fellows

Publikováno v: Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications ISBN: 9783319125671
Adventures Between Lower Bounds and Higher Altitudes

This survey is offered in honour of the special occasion of the birthday celebration of science and education pioneer Professor Juraj Hromkovic. In this survey, we review recent results on one-player flood-filling games on graphs, Flood-It and Free-F

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::b7c969c405a1c70fd295820a443f81c8
https://doi.org/10.1007/978-3-319-98355-4_20