Using BiasedRandomized Algorithms for the MultiPeriod Product Display Problem with Dynamic Attractiveness From brickandmortar stores to omnichannel retail, the efficient selection of products to be displayed on store tables, advertising brochures, or online front pages has become a critical issue. One possible goal is to maximize the overall attractivenessxe2x80x99 level of the displayed items, i.e., to enhance the shopping experience of our potential customers as a way to increase sales and revenue. With the goal of maximizing the total attractiveness value for the visiting customers over a multiperiod time horizon, this paper studies how to configure an assortment of products to be included in limited display spaces, either physical or online. In order to define a realistic scenario, several constraints are considered for each period and display table: (i) the inclusion of both expensive and nonexpensive products on the display tables; (ii) the diversification of product collections; and (iii) the achievement of a minimum profit margin. Moreover, the attractiveness level of each product is assumed to be dynamic, i.e., it is reduced if the product has been displayed in a previous period (loss of novelty) and vice versa. This generates dependencies across periods. Likewise, correlations across items are also considered to account for complementary or substitute products. In the case of brickandmortar stores, for instance, solving this rich multiperiod product display problem enables them to provide an exciting experience to their customers. As a consequence, an increase in sales revenue should be expected. In order to deal with the underlying optimization problem, which contains a quadratic objective function in its simplest version and a nonsmooth one in its complete version, two biasedrandomized metaheuristic algorithms are proposed. A set of new instances has been generated to test our approach and compare its performance with that of nonlinear solvers.

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.