Research Talk: Sequencing Stochastic Jobs with a Single SampleThis paper revisits the single machine scheduling problem to minimize total weighted completion times. The twist is that job sizes are stochastic from unknown distributions, and the scheduler has access to only a single sample from the distributions. For this restricted information regime, we analyze the simplest and probably only reasonable scheduling algorithm, namely to schedule by ordering the jobs by weight over sampled processing times. In general, this algorithm can be tricked by adversarial input distributions, performing in expectation arbitrarily worse even in comparison to choosing a random schedule. The paper suggests notions to capture the idea that this algorithm, on reasonable inputs, should exhibit a provably good expected performance.Read more- Research Talk: Dynamic random intersection graph: dynamic local convergence and giant structureLocal convergence of finite graphs was independently introduced by Benjamini and Schramm in 2001 and Aldous and Steele in 2004. Intuitively, it describes the resemblance of a neighborhood of a uniformly chosen vertex to a certain limiting graph. Local convergence has become a very important tool in sparse random graph theory, as many random graph properties turn out to be determined by the local limit. For instance, the asymptotic number of spanning trees and the partition function of the Ising model are computable in terms of the local limit. So far, local convergence has been mostly investigated in the context of static graphs. However, this notion can be naturally extended to the dynamic setting by applying the classic theory of convergence of stochastic processes. Thanks to this, the local convergence technique can be applied to tackle properties of dynamic graphs, such as membership in the giant component in a dynamic graph or epidemic evolution on dynamic graphs.Read more
