Informatik-Kolloquium: The Subset Sum Game Revisited

Montag, 16.10.2017, 16.15 Uhr

Ort: Seminarraum i1 (4017), Ahornstr. 55

Referent: Astrid Pieterse, TU Eindhoven

Abstract:

In this talk I will discuss a game theoretic variant of the subset sum problem, called the subset sum game. In this game, two players compete over a common resource, that is represented by a knapsack. Each player has its own set of items. Players alternately get to choose one of their items and put it in the knapsack, the game ends when none of the remaining items fit. A players goal is to maximize the total weight of the items it packs into the knapsack (selfish strategy), or to minimize the weight of its opponent (hostile strategy). In general, the maximum reachable weight of a player when playing against a selfish or hostile adversery cannot be approximated within any constant factor, unless P=NP. Furthermore, finding the best packing strategy is PSPACE complete in this setting. I will show in this talk that when playing against a greedy adversery, the game becomes easier and has a PTAS, but no FPTAS. Thereby this variant of the game forms one of the rare examples of pseudo-polynomially solvable problems that have a PTAS, but do not allow an FPTAS.

Es laden ein: Die Dozenten der Informatik