This talk addresses the problem to minimize the total expected completion time of a set of N non-preemptive jobs with stochastic processing times on a set of M identical machines. A special case that has recently gained attention is when the processing times follow Bernoulli distributions. It can be seen as a vanilla version of stochastic scheduling because of its clean combinatorics, while still preserving the core difficulties that make stochastic scheduling problems notoriously hard. Gupta et al. (SODA 23) exhibited an O(sqrt(M)) approximation algorithm, where the performance guarantee suppresses poly-logarithmic factors in the number of jobs. We show that the problem admits a PTAS, given that the number of different job processing times is bounded by a constant. The result rests on a series of transformations of an optimal scheduling policy to a well-formed scheduling policy that makes scheduling decisions at specific points in time only, while losing only a negligible factor in expected cost. An optimal well-formed policy is then computed by dynamic programming. Two technical issues are solved, namely (i) to ensure that, with a negligible delay, the transformed policy has an information advantage over the optimal policy, allowing it to simulate the decisions of that policy, and (ii) to ensure that the delays do not accumulate, thus solving the trade-off between the complexity of the scheduling policy and its expected cost. Our result implies a quasi-polynomial time O(log N) approximation when there is no bound on the number of different processing times.

In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. We seek a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm.

We give a general framework for devising approximation algorithms for stochastic minimum-norm optimization, using which we obtain approximation algorithms for the stochastic minimum-norm versions of the load balancing and spanning tree problems.

The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stopping, and Operations Research. A usual assumption in these works is that the probability distributions of the n underlying random variables are given as input to the algorithm. Since in practice these distributions need to be learned under limited feedback, we initiate the study of such stochastic problems in the Multi-Armed Bandits model.

In the Multi-Armed Bandits model we interact with n unknown distributions over T rounds: in round t we play a policy and only receive its value as feedback. The goal is to minimize the regret, which is the difference over T rounds in the total value of the optimal algorithm that knows the distributions vs. the total value of our algorithm that learns the distributions from the limited feedback. Our main results give near-optimal O(poly(n) * sqrt(T) * polylog(T)) total regret algorithms for both Prophet Inequality and Pandora's Box.

Our proofs proceed by maintaining confidence intervals on the unknown indices of the optimal policy. The exploration-exploitation tradeoff prevents us from directly refining these confidence intervals, so the main technique is to design a regret upper bound function that is learnable while playing low-regret Bandit policies.

Given subsets of uncertain values, we study the problem of identifying the subset of minimum total value by querying as few values as possible. This set selection problem falls into the field of explorable uncertainty and is of intrinsic importance therein as it implies strong adversarial lower bounds for a wide range of classical problems such as knapsack and matchings. We consider a stochastic problem variant and give algorithms that, in expectation, improve upon these adversarial lower bounds. The key to our results is to prove a strong structural connection to a seemingly unrelated covering problem with uncertainty in the constraints via a linear programming formulation. We exploit this connection to derive an algorithmic framework that can be used to solve both problems under uncertainty, obtaining nearly tight bounds on the competitive ratio. This is the first non-trivial stochastic result concerning the sum of unknown values without further structure known for the set and it may by useful for solving more general problems in the area of explorable uncertainty.