3-Dimensional Random Assignment Problems
Prof. Gregory Sorkin
The London School of Economics and Political Science (LSE)
The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to pi^2/6. In dimensions 3 and higher, there are natural Axial and Planar assignment generalizations. Both are NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do? The asymptotic behavior remains an open question. For 3-dimensional Planar assignment, we give a ln n approximation algorithm, and for Axial assignment, an unrelated n^eps approximation algorithm. In higher dimensions, both algorithms fail dismally.
Joint work with Alan Frieze.
Short bio: Professor Sorkin joined the Management Science Group at LSE in 2010 following 20 years at IBM Research, New York. He holds a PhD in Electrical Engineering and Computer Science from the University of California at Berkeley and an AB in Mathematics from Harvard. He is an IBM Master Inventor and made key contributions to the IBM Antivirus product, to optimising the manufacture of 'multilayer ceramic modules', and to a number of transportation optimisation projects for IBM and its clients.
Prof. Sorkin is visiting the department Jan 30 - Feb 3. He will act as the opponent in the public defence of Pekka Parviainen's doctoral thesis on Friday the 3rd of February.