Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.
Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.
Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.
Вот они, в хронологическом порядке:
Вычисление PageRank за сублинейное время. Christian Borgs, Michael Brautbar, Jennifer Chayes, и Shang-Hua Teng. arXiv:1202.2771 и WAW 2012 (9th Workshop on Algorithms and Models for the Web Graph). Этот алгоритм не намного быстрее линейного (он позволяет находить все страницы, pagerank которых больше Delta, за O(n/Delta)), но мне кажется интересной сама возможность доказывать такие оценки в естественной модели вычислений для графов страниц, связанных гиперссылками.
Нахождение «самой нечестной» монетки за наименьшее количество подбрасываний. Karthekeyan Chandrasekaran и Richard Karp, arXiv:1202.3639. Задача, решаемая в этой статье, является весьма фундаментальной, и результат — оптимальное решение, вместо известных до этого приближений с точностью до постоянного коэффициента.
Быстрый универсальный алгоритм для хеширования строк. Owen Kaser и Daniel Lemire, arXiv:1202.4961. Алгоритм для хеширования строк, использующий 0,2 такта процессорного времени на обработку одного байта и при этом имеющий гарантированные теоретически характеристики.
Известные алгоритмы для решения EDGE CLIQUE COVER, вероятно, оптимальны. Marek Cygan, Marcin Pilipczuk и Michał Pilipczuk, arXiv:1203.1754 и SODA 2013. Существует простой FPT алгоритм для покрытия ребер графа минимальным количеством клик, время работы которого, однако, пропорционально 22o(k)poly(n), где k — количество клик и n — количество вершин в графе. Несомненно, задача улучшения этой оценки стоит довольно давно. В прошлом году было показано, что лучшей кернелизации задачи достичь нельзя, а в этом препринте показано, что такая оценка оптимальна независимо от того, используем мы кернелизацию или нет. По крайней мере, при условии того, что верна гипотеза об экспоненциальном времени.
Аппроксимируемость решения задачи о вершинном покрытии в power law graphs. Mikael Gast и Mathias Hauptmann, arXiv:1204.0982. Мне кажется, должно быть больше работы над алгоритмами, которые используют свойства, которыми обладают графы страниц в Сети или пользователей в социальных сетях. Данный алгоритм — хороший пример: он улучает достижимую степень аппроксимации для задачи вершинного покрытия для любого графа, распределение степеней вершин в котором подчиняется степенному закону.
Кластеризация сложна только когда она не нужна. Amit Daniely, Nati Linial и Michael Saks, arXiv:1205.4891. Как и в предыдущей статье, в этой описан шаг от сложности задачи в общем случае к оценке сложности для некоторых более характерных экземпляров задачи. Главная идея в том, что сложными для алгоритмов кластеризации являются лишь те данные, которые с трудом поддаются кластеризации в принципе. Данное в статье определение «хорошей кластеризации», кажется, весьма чувствительно к данным со множеством выбросов или помех, но это вполне может стать темой дальнейшего изучения.
Рандомизированный параллельный алгоритм для решения системы линейных уравнений размером n x n за O(n2). Joerg Fliege, arXiv:1209.3995. Настоящий прорыв здесь заключен в алгоритме решения систем уравнений над конечными полями, созданном Prasad Raghavendra и описанном ранее в прошлом году в блоге Richard Lipton. В этой статье описано, как применить его к вещественным числам.
Улучшение оценки детерминированного решения динамической задачи о связности графа. Christian Wulff-Nilsen, arXiv:1209.5608 и SODA 2013. Представлена структура данных, поддерживающая выполнение запросов обновления (создание или удаление ребер) за амортизированное время O(log2n / log log n) и запросов вида «есть ли в графе путь между вершинами u и v» за O(log n/log log n) в худшем случае, где n — количество вершин в графе. (У Eppstein забавный каламбур — предыдущей лучшей оценкой для запроса на обновление графа было O(log2n) и этот результат — всего лишь log shaving (actually, log log shaving)).
8/5-аппроксимация решения задачи о коммивояжере. András Sebö, arXiv:1209.3523 и IPCO 2013. В данной статье речь идет о модификации задачи коммивояжера, при которой начальная и конечная точка его путешествия не обязательно совпадают. Я рассказывал студентам про алгоритм Кристофидеса достаточно раз, чтобы знать разницу между задачей о пути и цикле, но тот факт, что коэффициент приближения для оценки длины пути существенно больше, чем для оценки длины цикла, каким-то образом прошел мимо меня.
Приближение k-медиан псевдо-аппроксимацией. Shi Li и Ola Svensson, arXiv:1211.0243. Задача k-медиан здесь состоит в нахождении ровно k центров кластеров, минимизируя сумму расстояний от каждой точки до центра кластера, которому она принадлежит, приближение этой задачи заключается в нахождении k центров, минимизируя целевую функцию с некоторой точностью, а псевдо-аппроксимация — нахождение приблизительно k центров. Как пишут авторы, добавление даже одной дополнительной точки существенно меняет вид целевой функции, так что факт применимости псевдо-аппроксимации к этой задаче достаточно удивителен.
Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.
Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.
Вот они, в хронологическом порядке:
Вычисление PageRank за сублинейное время. Christian Borgs, Michael Brautbar, Jennifer Chayes, и Shang-Hua Teng. arXiv:1202.2771 и WAW 2012 (9th Workshop on Algorithms and Models for the Web Graph). Этот алгоритм не намного быстрее линейного (он позволяет находить все страницы, pagerank которых больше Delta, за O(n/Delta)), но мне кажется интересной сама возможность доказывать такие оценки в естественной модели вычислений для графов страниц, связанных гиперссылками.
Нахождение «самой нечестной» монетки за наименьшее количество подбрасываний. Karthekeyan Chandrasekaran и Richard Karp, arXiv:1202.3639. Задача, решаемая в этой статье, является весьма фундаментальной, и результат — оптимальное решение, вместо известных до этого приближений с точностью до постоянного коэффициента.
Быстрый универсальный алгоритм для хеширования строк. Owen Kaser и Daniel Lemire, arXiv:1202.4961. Алгоритм для хеширования строк, использующий 0,2 такта процессорного времени на обработку одного байта и при этом имеющий гарантированные теоретически характеристики.
Известные алгоритмы для решения EDGE CLIQUE COVER, вероятно, оптимальны. Marek Cygan, Marcin Pilipczuk и Michał Pilipczuk, arXiv:1203.1754 и SODA 2013. Существует простой FPT алгоритм для покрытия ребер графа минимальным количеством клик, время работы которого, однако, пропорционально 22o(k)poly(n), где k — количество клик и n — количество вершин в графе. Несомненно, задача улучшения этой оценки стоит довольно давно. В прошлом году было показано, что лучшей кернелизации задачи достичь нельзя, а в этом препринте показано, что такая оценка оптимальна независимо от того, используем мы кернелизацию или нет. По крайней мере, при условии того, что верна гипотеза об экспоненциальном времени.
Аппроксимируемость решения задачи о вершинном покрытии в power law graphs. Mikael Gast и Mathias Hauptmann, arXiv:1204.0982. Мне кажется, должно быть больше работы над алгоритмами, которые используют свойства, которыми обладают графы страниц в Сети или пользователей в социальных сетях. Данный алгоритм — хороший пример: он улучает достижимую степень аппроксимации для задачи вершинного покрытия для любого графа, распределение степеней вершин в котором подчиняется степенному закону.
Кластеризация сложна только когда она не нужна. Amit Daniely, Nati Linial и Michael Saks, arXiv:1205.4891. Как и в предыдущей статье, в этой описан шаг от сложности задачи в общем случае к оценке сложности для некоторых более характерных экземпляров задачи. Главная идея в том, что сложными для алгоритмов кластеризации являются лишь те данные, которые с трудом поддаются кластеризации в принципе. Данное в статье определение «хорошей кластеризации», кажется, весьма чувствительно к данным со множеством выбросов или помех, но это вполне может стать темой дальнейшего изучения.
Рандомизированный параллельный алгоритм для решения системы линейных уравнений размером n x n за O(n2). Joerg Fliege, arXiv:1209.3995. Настоящий прорыв здесь заключен в алгоритме решения систем уравнений над конечными полями, созданном Prasad Raghavendra и описанном ранее в прошлом году в блоге Richard Lipton. В этой статье описано, как применить его к вещественным числам.
Улучшение оценки детерминированного решения динамической задачи о связности графа. Christian Wulff-Nilsen, arXiv:1209.5608 и SODA 2013. Представлена структура данных, поддерживающая выполнение запросов обновления (создание или удаление ребер) за амортизированное время O(log2n / log log n) и запросов вида «есть ли в графе путь между вершинами u и v» за O(log n/log log n) в худшем случае, где n — количество вершин в графе. (У Eppstein забавный каламбур — предыдущей лучшей оценкой для запроса на обновление графа было O(log2n) и этот результат — всего лишь log shaving (actually, log log shaving)).
8/5-аппроксимация решения задачи о коммивояжере. András Sebö, arXiv:1209.3523 и IPCO 2013. В данной статье речь идет о модификации задачи коммивояжера, при которой начальная и конечная точка его путешествия не обязательно совпадают. Я рассказывал студентам про алгоритм Кристофидеса достаточно раз, чтобы знать разницу между задачей о пути и цикле, но тот факт, что коэффициент приближения для оценки длины пути существенно больше, чем для оценки длины цикла, каким-то образом прошел мимо меня.
Приближение k-медиан псевдо-аппроксимацией. Shi Li и Ola Svensson, arXiv:1211.0243. Задача k-медиан здесь состоит в нахождении ровно k центров кластеров, минимизируя сумму расстояний от каждой точки до центра кластера, которому она принадлежит, приближение этой задачи заключается в нахождении k центров, минимизируя целевую функцию с некоторой точностью, а псевдо-аппроксимация — нахождение приблизительно k центров. Как пишут авторы, добавление даже одной дополнительной точки существенно меняет вид целевой функции, так что факт применимости псевдо-аппроксимации к этой задаче достаточно удивителен.