TU Darmstadt / ULB / TUbiblio

The Minimum Feasible Tileset Problem

Disser, Y. ; Kratsch, S. ; Sorge, M. (2014)
The Minimum Feasible Tileset Problem.
12th Workshop on Approximation and Online Algorithms (WAOA 2014). Wrolaw, Poland (11.-12.09.2014)
doi: 10.1007/978-3-319-18263-6_13
Conference or Workshop Item, Bibliographie

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 parameterized with the number of scenarios and with the number of symbols.

Item Type: Conference or Workshop Item
Erschienen: 2014
Creators: Disser, Y. ; Kratsch, S. ; Sorge, M.
Type of entry: Bibliographie
Title: The Minimum Feasible Tileset Problem
Language: English
Date: 2014
Publisher: Springer
Book Title: Approximation and Online Algorithms
Series: Lecture Notes in Computer Science
Series Volume: 8952
Event Title: 12th Workshop on Approximation and Online Algorithms (WAOA 2014)
Event Location: Wrolaw, Poland
Event Dates: 11.-12.09.2014
DOI: 10.1007/978-3-319-18263-6_13
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 parameterized with the number of scenarios and with the number of symbols.

Divisions: Exzellenzinitiative
Exzellenzinitiative > Graduate Schools
Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics
04 Department of Mathematics > Optimization
04 Department of Mathematics > Optimization > Discrete Optimization
Date Deposited: 14 Oct 2016 07:28
Last Modified: 18 Aug 2022 12:28
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details