Приближение числа раскрасок, кажется, легко на второстепенных исключенных графах, используя алгоритм Юнга / Шаха. Каковы другие примеры проблем, которые сложны для общих графов, но просты для второстепенных исключенных графов? Обновление 10/24 Кажется, следуя результатам Гроэ, формула, которая...
Существует ли интересный пример рандомизированного алгоритма для задачи поиска, который всегда выводит один и тот же (правильный) ответ, независимо от его внутренней случайности, но который использует случайность так, что его ожидаемое время выполнения лучше, чем время выполнения самого быстрого из...
Меня довольно смущает литература по непрерывной оптимизации и литература TCS о том, какие типы (непрерывных) математических программ (МП) могут быть эффективно решены, а какие нет. Сообщество непрерывной оптимизации, кажется, утверждает, что все выпуклые программы могут быть решены эффективно, но я...
В 1980-х годах появились модели параллельных вычислений PRAM и BSP . Кажется, что расцвет обеих моделей был в конце 80-х и начале 90-х годов. Эти области все еще активны с точки зрения исследования параллельных алгоритмов? Существуют ли более новые, более сложные модели для параллельных вычислений?...
Для решения проблемы максимального потока , кажется, существует ряд очень сложных алгоритмов, по крайней мере один из которых был разработан совсем недавно, в прошлом году. Макс Орлина течет за O (MN) времени или лучше дает алгоритм, который работает в O (VE). С другой стороны, алгоритмы, которые я...
Я преподаю курс продвинутых алгоритмов и хотел бы включить некоторые темы, связанные с машинным обучением, которые будут интересны моим студентам. В результате я хотел бы услышать мнение людей о наиболее интересных / лучших алгоритмических результатах в области машинного обучения. Потенциально...
Строка имеет подпоследовательностей, но обычно они не все различны. Какова сложность нахождения максимальной частоты любой подпоследовательности?2n2n2^n Например, строка «подпоследовательность» содержит 7 копий подпоследовательности «иск», и это максимум. Пример кода перебора на...
Следующая проблема возникла во время исследования, и она удивительно чиста: У вас есть источник монет. Каждая монета имеет уклон, а именно вероятность того, что она упадет на «голову». Для каждой монеты независимо существует вероятность 2/3, что она имеет смещение не менее 0,9, а с остальной...
Были два вопросы недавно спросил о cs.se , которые были либо связанные или имели особый случай , эквивалентный следующему вопросу: Предположим, у вас есть последовательность из n чисел, такая что ∑ n i = 1 a i = n ( n + 1 ) . Разложите его в сумму двух перестановок, π и , из , так что...
Я читал лекцию по сортировке блинов и сказал, что: Сортировка по обращению является NP-трудной «подписан» сортировка по разворотов в P . Что заставило меня задуматься. В некотором смысле «подписанная» сортировка является «направленной» - вы можете рассматривать знак как направление (и...
Я ищу хорошие примеры, где встречается следующее явление: (1) Алгоритмическая проблема выглядит сложной, если вы хотите решить ее, работая из определений и используя только стандартные результаты. (2) С другой стороны, это становится легко, если вы знаете некоторые (не очень стандартные) теоремы....
Пусть класс A обозначает все графы размера которые имеют гамильтонов цикл. Из этого класса легко получить случайный граф - возьмите n изолированных узлов, добавьте случайный гамильтонов цикл и затем случайным образом добавьте ребра.nnnnnn Пусть класс B обозначает все графы размера которых нет...
Предположим, у меня есть poset "S" и монотонный предикат "P" на S. Я хочу найти один или все максимальные элементы S, удовлетворяющие P. EDIT : Я заинтересован в минимизации количества оценок P . Какие алгоритмы существуют для этой проблемы и какие свойства и дополнительные операции они требуют на...
В ISGCI списки более 1100 классов графов. Для многих из них мы знаем, можно ли выбрать НЕЗАВИСИМЫЙ НАБОР за полиномиальное время; их иногда называют классами IS-easy . Я хотел бы составить список максимальных классов IS-easy. Эти классы вместе образуют границу (известной) управляемости для этой...
Изменить: я выбираю ответ с наибольшим количеством баллов до 6 декабря 2012 года. Это мягкий вопрос. Концепция (детерминированных) алгоритмов восходит к BC. Как насчет вероятностных алгоритмов? В этой статье в вики в качестве первого рандомизированного алгоритма (год ???) был задан алгоритм Рабина...
Я только что преподавал рандомизированный алгоритм сокращений по методу Каргера-Стейна в своем выпускном классе алгоритмов. Это настоящая алгоритмическая жемчужина , поэтому я не могу ее не преподавать, но она всегда расстраивает меня, потому что я не знаю других применений основной техники. (Таким...
Если неориентированный -регулярный граф и представляет собой подмножество вершин мощности , вызови расширение края в г. количестваd S ≤ | V | / 2 SG=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac {Edges(S,V-S)}{d\cdot...
К моему удивлению, я не смог найти статьи об этом - вероятно, искал не те ключевые слова. Итак, у нас есть массив чего угодно и функция по его индексам; - перестановка.фееfееf Как переупорядочить массив в соответствии с с памятью и временем выполнения, максимально приближенными к и ?O ( 1 ) O ( n...
Некоторое время я думал о следующей проблеме, и я не нашел ее полиномиального решения. Только грубая четверка. Я тоже пытался свести к этому проблему NP-Complete, но безуспешно. Вот проблема : У вас есть отсортированный набор пар целых положительных чисел....
Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...