Jan Vondrák

Jan Vondrák works on algorithms for optimization problems, especially those involving submodular functions. Of recent interest is a collection of submodular partitioning problems arising in computer vision, and a general methodology to prove the optimality of approximation factors for such problems. Vondrák is also working on algorithms for constructing objects whose existence is guaranteed by non-constructive proofs such as the Lovasz local lemma.