Топ-10 результатов в области алгоритмов за 2012 год

Каждый год 31 декабря David Eppstein ^[1] публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org ^[2]. По ссылкам можно познакомиться с материалами за 2010 ^[3] и 2011 ^[4] (мой перевод ^[5]) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мой собственные работы и некоторые другие, о которых я писал раньше ^[6]. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока ^[7]), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке:

Вычисление PageRank ^[8] за сублинейное время. Christian Borgs, Michael Brautbar, Jennifer Chayes, и Shang-Hua Teng. arXiv:1202.2771 ^[9] и WAW 2012 (9th Workshop on Algorithms and Models for the Web Graph). Этот алгоритм не намного быстрее линейного (он позволяет находить все страницы, pagerank которых больше Delta, за O(n/Delta)), но мне кажется интересной сама возможность доказывать такие оценки в естественной модели вычислений для графов страниц, связанных гиперссылками.

Нахождение «самой нечестной» монетки за наименьшее количество подбрасываний. Karthekeyan Chandrasekaran и Richard Karp ^[10], arXiv:1202.3639 ^[11]. Задача, решаемая в этой статье, является весьма фундаментальной, и результат — оптимальное решение, вместо известных до этого приближений с точностью до постоянного коэффициента.

Быстрый универсальный алгоритм для хеширования строк. Owen Kaser и Daniel Lemire, arXiv:1202.4961. ^[12] Алгоритм для хеширования строк, использующий 0,2 такта процессорного времени на обработку одного байта и при этом имеющий гарантированные теоретически характеристики.

Известные алгоритмы для решения EDGE CLIQUE COVER, вероятно, оптимальны. Marek Cygan ^[13], Marcin Pilipczuk ^[14] и Michał Pilipczuk ^[15], arXiv:1203.1754 ^[16] и SODA 2013 ^[17]. Существует простой FPT ^[18] алгоритм для покрытия ребер графа минимальным количеством клик, время работы которого, однако, пропорционально 2^2o(k)poly(n), где k — количество клик и n — количество вершин в графе. Несомненно ^[19], задача улучшения этой оценки стоит довольно давно. В прошлом году было показано, что лучшей кернелизации ^[20] задачи достичь нельзя, а в этом препринте показано, что такая оценка оптимальна независимо от того, используем мы кернелизацию или нет. По крайней мере, при условии того, что верна гипотеза об экспоненциальном времени. ^[21]

Аппроксимируемость решения задачи о вершинном покрытии в power law ^[22] graphs. Mikael Gast и Mathias Hauptmann, arXiv:1204.0982 ^[23]. Мне кажется, должно быть больше работы над алгоритмами, которые используют свойства, которыми обладают графы страниц в Сети или пользователей в социальных сетях. Данный алгоритм — хороший пример: он улучает достижимую степень аппроксимации для задачи вершинного покрытия для любого графа, распределение степеней вершин в котором подчиняется степенному закону.

Кластеризация сложна только когда она не нужна. Amit Daniely, Nati Linial и Michael Saks, arXiv:1205.4891 ^[24]. Как и в предыдущей статье, в этой описан шаг от сложности задачи в общем случае к оценке сложности для некоторых более характерных экземпляров задачи. Главная идея в том, что сложными для алгоритмов кластеризации являются лишь те данные, которые с трудом поддаются кластеризации в принципе. Данное в статье определение «хорошей кластеризации», кажется, весьма чувствительно к данным со множеством выбросов или помех, но это вполне может стать темой дальнейшего изучения.

Рандомизированный параллельный алгоритм для решения системы линейных уравнений размером n x n за O(n²). Joerg Fliege, arXiv:1209.3995 ^[25]. Настоящий прорыв здесь заключен в алгоритме решения систем уравнений над конечными полями, созданном Prasad Raghavendra и описанном ранее ^[26] в прошлом году в блоге Richard Lipton. В этой статье описано, как применить его к вещественным числам.

Улучшение оценки детерминированного решения динамической задачи о связности графа. Christian Wulff-Nilsen, arXiv:1209.5608 ^[27] и SODA 2013. Представлена структура данных, поддерживающая выполнение запросов обновления (создание или удаление ребер) за амортизированное время O(log²n / log log n) и запросов вида «есть ли в графе путь между вершинами u и v» за O(log n/log log n) в худшем случае, где n — количество вершин в графе. (У Eppstein забавный каламбур — предыдущей лучшей оценкой для запроса на обновление графа было O(log²n) и этот результат — всего лишь log shaving ^[28] (actually, log log shaving)).

8/5-аппроксимация решения задачи о коммивояжере ^[29]. András Sebö, arXiv:1209.3523 ^[30] и IPCO 2013 ^[31]. В данной статье речь идет о модификации задачи коммивояжера, при которой начальная и конечная точка его путешествия не обязательно совпадают. Я рассказывал студентам про алгоритм Кристофидеса ^[32]достаточно раз, чтобы знать разницу между задачей о пути и цикле, но тот факт, что коэффициент приближения для оценки длины пути существенно больше, чем для оценки длины цикла, каким-то образом прошел мимо меня.

Приближение k-медиан псевдо-аппроксимацией. Shi Li и Ola Svensson, arXiv:1211.0243 ^[33]. Задача k-медиан здесь состоит в нахождении ровно k центров кластеров, минимизируя сумму расстояний от каждой точки до центра кластера, которому она принадлежит, приближение этой задачи заключается в нахождении k центров, минимизируя целевую функцию с некоторой точностью, а псевдо-аппроксимация — нахождение приблизительно k центров. Как пишут авторы, добавление даже одной дополнительной точки существенно меняет вид целевой функции, так что факт применимости псевдо-аппроксимации к этой задаче достаточно удивителен.

Автор: AlexErofeev

Источник ^[34]