   |
|
|
||||
|
||||
|
|
|
||
|
||||
|
||||
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
||||
|
|
LETTER FROM PROF. KAREN AARDAL
Jaroslaw Byrka obtained his PhD degree under my supervision at Eindhoven Institute of Technology (TU/e) in 2008, after holding a Marie Curie scholarship at Centrum Wiskunde & Informatica (CWI) in Amsterdam, The Netherlands, and a PhD position at TU/e. After that, he held postdoc positions at TU/e and EPFL in Lausanne until recently returning to Wroclaw, Poland. Dr Byrka has obtained some remarkable results. One of the very central problems in combinatorial optimization is the uncapacitated facility location problem. It was first formulated and analyzed in the literature in the 1960s. In the beginning of the 1980s an approximation algorithm with a logarithmic worst-case performance guarantee was developed, and it remained an important open question whether there exists an approximation algorithm with a constant performance guarantee. This was answered in the affirmative in 1997 for the case that the assignment costs satisfy the triangle inequality. When Byrka started his PhD studies the best guarantee was close to the lower bound on approximability but the gap was not closed. It seemed very difficult to make any progress. Shortly after starting his studies, Byrka proved that the analysis of the current best algorithm was not tight, which gave several new insights. Subsequently, he designed an improved algorithm and thereby cut the gap between upper and lower bound of approximability by 1/3. His algorithm stands as the best to this day and was recently published in SIAM Journal on Computing. He has, together with different groups of co-authors, obtained several important results for other facility location problems as well, and for problems in a broad range of other areas such as computational biology and Steiner trees. The paper on Steiner trees is highly acclaimed and was awarded the Best Paper Award at the 2010 STOC Conference. Dr Byrka has the enviable capability to constantly renew himself, and to work with different colleagues on very different problems simultaneously. Next to being a strong researcher he is a very nice and loyal colleague. He is a truly worthy winner of the Witold Lipski prize.
Prof. Karen Aardal Delft Institute of Applied Mathematics Delft Institute of Technology |
|
|
|
||||
