У Milanin была работа по компонентам трехсвязности (а также соответствующая задача)

Вот еще от Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. На CF Ilya Razenshteyn (ilyaraz): http://research.microsoft.com/apps/pubs/default.aspx?id=144833

.

.

marek.cygan очень крутой, вот список публикаций: http://dblp.uni-trier.de/pers/hd/c/Cygan:Marek.html

Я был на защите кандидатской у natalia — слышал только лестные отзывы. Я в этой теме не понимаю, но как понял она решила в общем виде задачу, которую существенное время не могли решить в этой области.

А вот вам rpeng: http://math.mit.edu/~rpeng/publications.html

На самом деле примеров довольно много, хотя, конечно, большинство в индустрию уходят.

Говорят пара неплохих публикаций есть у этого паренька -> Darooha.

Тут небольшая часть того, в чем участвовал Максим Бабенко: http://arxiv.org/find/all/1/all:+AND+Maxim+Babenko/0/1/0/all/0/1

A somewhat related thread: https://www.quora.com/Where-are-the-medalists-of-2000-2005-ACM-ICPC-finals-now. Many of the past ACMers who went into academia are mentioned there and their corresponding thesis titles can be found by searching their name.

У меня была работа, связанная с пополнением частичных латинских квадратов с использованием K различных цветов. Реализовывал поиск точного решения с помощью перебора с отсечениями (как выяснилось в итоге, для квадратов порядка N, когда использовать можно все N цветов для пополнения (т.е. K=N), и при небольших модификациях получается задача по разгадыванию судоку =)) пока не нашел ни одного, который разгадывался бы дольше чем 0.1 сек). Также исследовал приближенные алгоритмы решения с точностью 1/2 (т.е. гарантируется пополнение не меньше 50% свободных клеток относительно максимально возможного количества пополняемых клеток) и точностью (1-1/e), где используются подходы линейного программирования.

P.S.

Кому интересна эта тематика, советую почитать:

1) Gomes C.P., Regis R.G., Shmoys D.B. An improved approximation algorithm for the partial Latin square extension problem. // Operation Research Letters. – 2004. – V.32(5). – P. 479-484.

2) Hajirasouliha I., Kumar R., Sundaram R. On completing Latin squares. // STACS 2007, LNCS 4393. – 2007. – V.24. – P. 524-535.

3) Colbourn C.J. The complexity of completing partial latin squares. // Discrete Applied Mathematics. – 1984. – V.8. – P. 25-30.

4) Kumar R., Russel A., Sundaram R. Approximating latin square extensions. // Algorithmica. – 1999. – V.24(2). – P. 128-138.

Задача про судоку :))

тыц

Многие ACM-щики успешно закончили универ по профильному направлению...