The Linear Ordering Problem is a hard combinatorial optimization problem with applications in a number of disciplines. In this talk we will describe local search for the Linear Ordering Problem using permutation neighborhoods, and introduce a novel search procedure that improves on the state-of-the-art for greedy local search on a benchmark problem set. We will then move on to the problem of statistical machine translation. We will relate machine translation decoding to difficult combinatorial optimization problems and introduce a new model of word reordering using the linear ordering problem. This will lead to an interesting machine learning problem, which requires adaptation of standard learning algorithms. We will evaluate the learning methods on the task of German-English translation and show that the learned reordering models can help to significantly improve upon the translations of a standard decoder.
Roy Tromble is a Ph.D. candidate in the Department of Computer Science and the Center for Language and Speech Processing at Johns Hopkins University. He was born in Juneau, Alaska, graduated from Juneau-Douglas High School in 1997, and received B.S. degrees in Mathematics and Computer Science from the University of Idaho in 2001. He now resides in Pittsburgh where he will work for Google.