Uriel Feige is a professor at the Weizmann Institute, though this work was done while he was a member of the theory group at Microsoft Research. His main research interests involve studying the borderline between P and NP as it manifests itself in approximation algorithms, heuristics, and exact algorithms that are not necessarily polynomial time.

Jan Vondrák is a researcher at the IBM Almaden research center. His interests are in approximation algorithms and probabilistic combinatorics. He graduated from M.I.T. in 2005 under the supervision of Michel Goemans. Subsequently he spent a year at Microsoft Research in Redmond where this work originated. Matroids and submodular functions have pervaded his research ever since.