The core concept for the multidimensional knapsack problem We present the newly developed core concept for the Multidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the onedimensional case. The core for the multidimensional problem is defined in dependence of a chosen efficiency function of the items, since no single obvious efficiency measure is available for MKP. An empirical study on the cores of widelyused benchmark instances is presented, as well as experiments with different approximate core sizes. Furthermore we describe a memetic algorithm and a relaxation guided variable neighborhood search for the MKP, which are applied to the original and to the core problems. The experimental results show that given a fixed runtime, the different metaheuristics as well as a general purpose integer linear programming solver yield better solution when applied to approximate core problems of fixed size.

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.