Conference paper
Matroid matching: The power of local search
Jon Lee, Maxim Sviridenko, et al.
STOC 2010
In this paper we consider a generalized version of the classical preemptive open shop problem with sum of weighted job completion times objective. The main result is a (2 + ε)-approximation algorithm for this problem. In the last section we also discuss the possibility of improving our algorithm. © 2002 Elsevier Science (USA). All rights reserved.
Jon Lee, Maxim Sviridenko, et al.
STOC 2010
Warren Schudy, Maxim Sviridenko
SODA 2012
Maurice Queyranne, Maxim Sviridenko
Journal of Scheduling
Jon Lee, Vahab S. Mirrokni, et al.
SIAM Journal on Discrete Mathematics