The bin packing problem is a well-studied problem in combinatorial optimization. In the
classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to …

Locally Checkable Labeling (LCL) problems include essentially all the classic problems of
$\mathsf {LOCAL} $ distributed algorithms. In a recent enlightening revelation, Chang and …

We propose a new algorithmic framework, called partial rejection sampling, to draw samples
exactly from a product distribution, conditioned on none of a number of bad events …

The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool
of the probabilistic method that allows one to prove that a set of n" bad" events do not …

In (Ref. 1),(Ref. 2) it was noticed that sometimes it takes BGP a substantial amount of time
and messages to converge and stabilize following the failure of some node in the Internet. In …

We give a Markov chain based algorithm for sampling almost uniform solutions of constraint
satisfaction problems (CSPs). Assuming a canonical setting for the Lovász local lemma …

We give an algorithmic local lemma by establishing a sufficient condition for the uniform
random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's …

We give a Markov chain based perfect sampler for uniform sampling solutions of constraint
satisfaction problems (CSP). Under some mild Lov\'asz local lemma conditions where each …

Multidimensional packing problems generalize the classical packing problems such as Bin
Packing, Multiprocessor Scheduling by allowing the jobs to be d-dimensional vectors. While …

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma
(LLL), there has been a plethora of results analyzing local search algorithms for various …