Вопросы об алгоритмах аппроксимации.
Известно, что некоторые проблемы неразрешимы, но, тем не менее, можно добиться определенного прогресса в их решении. Например, проблема остановки неразрешима, но можно добиться практического прогресса в создании инструментов для обнаружения потенциальных бесконечных циклов в вашем коде. Проблемы с...
У меня всегда были проблемы с пониманием важности разрыва целостности (IG) и ограничений на него. IG - это отношение (качества) оптимального целочисленного ответа к (качеству) оптимального реального решения релаксации задачи. Давайте рассмотрим покрытие вершин (VC) в качестве примера. VC можно...
Известно, что показатель TSP может быть аппроксимирован в пределах и не может быть аппроксимирован лучше, чем за полиномиальное время. Известно ли что-нибудь о поиске аппроксимационных решений за экспоненциальное время (например, менее шагов только с полиномиальным пространством)? Например, в какое...
Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач...
Пусть - граф с весовой функцией . Задача max-cut состоит в том, чтобы найти: если весовая функция неотрицательна (т. е. w (e) \ geq 0 для всех e \ in E ), тогда для max-cut существует много чрезвычайно простых 2-приближений. Например, мы можем:G=(V,E,w)G = (V, E, w)w:E→Rw:E\rightarrow...
Обычно думают о приближенных решениях (с гарантиями) NP-трудных задач. Проводятся ли какие-либо исследования по приближенным задачам, о которых уже известно, что они находятся в P? Это может быть хорошей идеей по нескольким причинам. Вдобавок ко всему, алгоритм аппроксимации может работать с...
Обычно считается маловероятным, что квантовые компьютеры смогут эффективно решать NP-полные задачи. В классическом случае одним из подходов к решению таких проблем является использование приближенных алгоритмов. Проводились ли какие-либо исследования алгоритмов аппроксимации с использованием...
Знаете ли вы какие-либо современные вики, посвященные задачам оптимизации NP, с их наилучшим приближением и результатом твердости? Судя по отзывам, можно предположить, что такого ресурса нет (см. В конце этого вопроса два близких варианта). - добавлено 8 февраля. Поскольку за последние два...
Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.kkkfff Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью...
Предположим, что мы решили проблему подсчета правильных раскрасок путем подсчета взвешенных раскрасок следующим образом: каждая правильная раскраска получает вес 1, а каждая неправильная раскраска получает вес где c - некоторая постоянная, а v - число ребер с конечными точками, окрашенными...
Я разместил это ранее на MSE, но было предложено, что здесь может быть лучшее место, чтобы спросить. Теорема универсального приближения утверждает, что «стандартная многослойная сеть прямой связи с одним скрытым слоем, которая содержит конечное число скрытых нейронов, является универсальным...
Мы знаем, что максимальный независимый набор (MIS) трудно аппроксимировать с коэффициентом для любого если P = NP. Какие существуют специальные классы графов, для которых известны лучшие алгоритмы аппроксимации?N1 - ϵn1−ϵn^{1-\epsilon}ε > 0ϵ>0\epsilon > 0 Каковы графики, для которых известны...
В 1999 году Петра Шурман и Герхард Дж. Вёгингер опубликовали статью «Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач» . С тех пор, насколько мне известно, обзоры, которые касались бы одного и того же списка проблем, не появлялись. Таким образом,...
При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.) Существуют ли хорошие образовательные источники или обзоры, выходящие...
В последнее время я начал изучать алгоритмы аппроксимации для NP-сложных задач и интересовался теоретическими причинами их изучения. (Вопрос не должен быть подстрекательским - мне просто любопытно). Из исследования алгоритмов аппроксимации возникла действительно прекрасная теория - связь между...
O(nlogn)O(nlogn)O(n\log n)1+O(n−c)1+O(n−c)1+O(n^{-c})cccO(n)O(n)O(n)(max−min)n−(c+1)(max−min)n−(c+1)(\max-\min)n^{-(c+1)}его первоначального значения, а затем используйте основную сортировку. Но модели с округлением имеют проблематичную теорию сложности, и это заставило меня задуматься, а как...
Для конкретности рассмотрим LP для решения игры с нулевой суммой для двух игроков, где у каждого игрока есть действий. Предположим, что каждая запись матрицы выплат имеет самое большее 1 в абсолютном значении. Для простоты давайте не будем делать предположений об ограниченности.nnnAAA Предположим,...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Когда мы рассматриваем алгоритм аппроксимации для задачи минимизации, разрыв интегральности IP-формулировки для этой задачи дает нижнюю границу отношения аппроксимации для определенного класса алгоритмов (таких как алгоритм округления или простой двойственный алгоритм). На самом деле существует...
Задача, которую мы здесь рассматриваем, - это расширение хорошо известной проблемы интервальной раскраски. Вместо интервалов мы рассматриваем прямоугольники, стороны которых параллельны осям. Цель состоит в том, чтобы закрасить прямоугольники минимальным количеством цветов, чтобы любые два...