The subset sum game revisited 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 PSPACEcomplete, and that against these adversaries the optimal reachable item weight for a player cannot be approximated within any constant factor (unless PNP). The game becomes easier when the adversary is shortsighted and plays greedily: finding the best packing strategy against a greedy adversary is NPcomplete in the weak sense. This variant forms one of the rare examples of pseudopolynomially solvable problems that have a PTAS, but do not allow an FPTAS.

Online Multistage Subset Maximization Problems. Numerous combinatorial optimization problems (knapsack, maximumweight matching, etc.) can be expressed as emphsubset maximization problems: One is given a ground set N1,dots,n, a collection mathcalFsubseteq 2N of subsets thereof such that emptysetinmathcalF, and an objective (profit) function p:mathcalFrightarrowmathbbR_. The task is to choose a set SinmathcalF that maximizes p(S). We consider the emphmultistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function p_t (and possibly the set of feasible solutions mathcalF_t) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the tradeoff between good pertime solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the emphonline setting, that is, p_t (along with possibly mathcalF_t) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constantcompetitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.