###
**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 |

**Options (only for editors)**

Show editorial Details |