The subset sum game revisited

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Downloads (Pure)

Samenvatting

We discuss a game theoretic variant of the subset sum problem, in which two players compete for a common resource represented by a knapsack. Each player owns a private set of items, players pack items alternately, and each player either wants to maximize the total weight of his own items packed into the knapsack or to minimize the total weight of the items of the other player.

We show that finding the best packing strategy against a hostile or a selfish adversary is PSPACE-complete, and that against these adversaries the optimal reachable item weight for a player cannot be approximated within any constant factor (unless P=NP). The game becomes easier when the adversary is short-sighted and plays greedily: finding the best packing strategy against a greedy adversary is NP-complete in the weak sense. This variant forms one of the rare examples of pseudo-polynomially solvable problems that have a PTAS, but do not allow an FPTAS.

Originele taal-2Engels
TitelAlgorithmic Decision Theory
Subtitel5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings
RedacteurenJorg Rothe
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's228-240
Aantal pagina's13
ISBN van elektronische versie978-3-319-67504-6
ISBN van geprinte versie978-3-319-67503-9
DOI's
StatusGepubliceerd - 2017
Evenement5th International Conference on Algorithmic Decision Theory (ADT 2017) - Luxembourg, Luxemburg
Duur: 25 okt 201727 okt 2017
Congresnummer: 5
https://sma.uni.lu/adt2017/

Publicatie series

NaamLecture Notes in Computer Science
UitgeverijSpringer Link
Volume10576

Congres

Congres5th International Conference on Algorithmic Decision Theory (ADT 2017)
Verkorte titelADT 2017
LandLuxemburg
StadLuxembourg
Periode25/10/1727/10/17
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'The subset sum game revisited'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Pieterse, A., & Woeginger, G. J. (2017). The subset sum game revisited. In J. Rothe (editor), Algorithmic Decision Theory: 5th International Conference, ADT 2017, Luxembourg, Luxembourg, October 25–27, 2017, Proceedings (blz. 228-240). (Lecture Notes in Computer Science; Vol. 10576). Springer. https://doi.org/10.1007/978-3-319-67504-6_16