The minimum feasible tileset problem

Y Disser, S Kratsch, M Sorge - International Workshop on Approximation …, 2014 - Springer
Abstract We consider the Minimum Feasible Tileset problem: Given a set of symbols and
subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols
(tiles) such that each scenario can be formed by selecting at most one symbol from each tile.
We show that this problem is NP-complete even if each scenario contains at most three
symbols. Our main result is a 4/3-approximation algorithm for the general case. In addition,
we show that the Minimum Feasible Tileset problem is fixed-parameter tractable both when …

The Minimum Feasible Tileset Problem

Y Disser, S Kratsch, M Sorge - Algorithmica, 2019 - Springer
We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and
subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols
(tiles) such that each scenario can be formed by selecting at most one symbol from each tile.
We show that this problem is APX APX-hard and that it is NP NP-hard even if each scenario
contains at most three symbols. Our main result is a 4/3-approximation algorithm for the
general case. In addition, we show that the Minimum Feasible Tileset problem is fixed …
Showing the best results for this search. See all results