Я ищу результаты твердости по раскраске вершин графов с ограниченной степенью. Учитывая граф , мы знаем, что для любого ϵ > 0 трудно приблизить χ ( G ) с множителем | V | 1 - ϵ, если NP = ZPP [ 1 ]. Но что, если максимальная степень G ограничена d ? Существуют ли в этом случае коэффициенты...
Сглаженный анализ был применен много раз, чтобы понять время выполнения точных алгоритмов для многих задач, таких как линейное программирование и k-средних. В этой области есть довольно общие результаты, например, Хейко Рёглин и Бертольд Вёкинг, Сглаженный анализ целочисленного программирования ,...
Я ищу класс сложности, который относится к APX, так как BPP относится к P. Я уже задавал этот же вопрос здесь , но, возможно, TCS будет более плодотворным местом для ответов. Причина этого вопроса заключается в том, что в практических задачах часто приходится находить приблизительные ответы...
Игры с двумя пруверами в один раунд (2P1R) являются важным инструментом для определения приближенности. В частности, параллельное повторение однокруговых игр с двумя проверками дает возможность увеличить размер пропуска в версии решения задачи аппроксимации. См . Обзорный доклад Ран Раза на КХЦ...
Что в настоящее время известно о приближаемости проблемы рода? Предварительный поиск говорит мне , что постоянное приближение фактора тривиально для достаточно плотных графов, и -приближение алгоритм было исключено. Является ли эта информация актуальной или известны более точные...
Для заданного графа в задаче сепаратора задается вопрос, существует ли вершина или множество ребер малой мощности (или веса), удаление которых разбивает на два непересекающихся графа приблизительно равных размеров. Это называется проблемой разделения вершин, когда удаленный набор является набором...
Я не смог найти в литературе точную характеристику исчезновения разрыва двойственности СДП. Или когда держится «сильная двойственность»? Например, когда кто-то переходит между Лассерром и SDP SDP, в принципе у него есть пробел в дуальности. Однако, почему-то, кажется, есть какая-то «тривиальная»...
Я слышал о результате в приблизительной окраске графика, но не могу найти источник. Результат: Для каждой константы существует достаточно большое k, такое, что раскраска k- раскрашиваемого графа в h k цветов NP-трудна.часhhКkkКkkч кhkhk Может ли кто-нибудь указать мне соответствующую...
Сложно ли приблизить приблизительное дробное хроматическое число на графах с ограниченными
Рассмотрим проблему доминирующего множества в общих графах, и пусть будет количеством вершин в графе. Алгоритм жадного приближения дает гарантию приближения фактора , т. Е. В полиномиальное время можно найти решение такое, что , где - размер минимального доминирующего множества. Есть оценки ,...
Многие здесь, вероятно, знают о недавних суперлинейных нижних оценках Алона для сетей в естественной геометрической обстановке [PDF] . Я хотел бы знать, что, во всяком случае, такая нижняя граница подразумевает в отношении аппроксимируемости связанных задач Set Cover / Hitting Set. ϵϵ\epsilon Чтобы...
Позволять FFF быть семьей dddподмножества конечной вселенной UUUобъектов. СемьяHHH из kkkподмножества UUU, с 1≤k<d1≤k<d1 \le k < d, это (k,d)(k,d)(k,d)- наезд набора изFFF если для каждого V∈FV∈FV \in F существует хотя бы один набор W∈HW∈HW \in H такой, что W⊂VW⊂VW \subset V, Учитывая...
В задаче Макс-Кута ищется подмножество S вершин данного простого неориентированного графа так, чтобы число ребер между S и дополнением к S было как можно большим. Max-Cut является APX-полным на графах с ограниченной степенью [PY91] и фактически APX-полным на кубических графах (т.е. графах степени...
Я пытаюсь показать, что определенная проблема недопустима из-за сокращения охвата. Мое сокращение превращает экземпляр с базовым набором размера и устанавливает в экземпляр моей проблемы, где определенный параметр имеет размер . Затем я могу показать, что экземпляр установленного покрытия, где...
В задаче о посаженной клике необходимо восстановить -клику, заложенную в случайном графе Эрдоша-Реньи . В основном это рассматривалось для , и в этом случае известно, что оно решаемо за полиномиальное время, если и предположило трудно для .КkkG ( n , p )г(N,п)G(n,p)р =12пзнак равно12p=\frac{1}{2}к...
Мне интересно, есть ли у следующей проблемы имя или какие-либо результаты, связанные с ним. Пусть - взвешенный граф, где обозначает вес ребра между и , и для всех , . Задача состоит в том, чтобы найти подмножество вершин, которое максимизирует сумму весов смежных с ними ребер: Обратите внимание,...
Рассмотрим классическую # P-полную задачу # 3SAT, т. Е. Посчитаем количество оценок, чтобы сделать 3CNF с переменными выполнимыми. Меня интересует аддитивная аппроксимируемость. Ясно, что существует тривиальный алгоритм для достижения -ошибки, но если , возможно ли иметь эффективный алгоритм...
Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей...