Stochastic Online Metric Matching We study the minimumcost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching.  :70,stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight O(log n)competitiveness for the randomorder arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of O(log n) has long been conjectured and remains a tantalizing open question.  :132,this paper, we show improved results in the i.i.d arrival model. We show how the i.i.d model can be used to give substantially better algorithms: our main result is an O((log log log n)2)competitive algorithm in :132,this model. Along the way we give a 9competitive algorithm for the line and tree metrics. Both results imply a strict separation between the i.i.d model and the adversarial and random order models, both for general metrics and these muchstudied metrics.

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.