Вопросы с тегом «approximation»

Я ищу алгоритм для распределения значений из списка, чтобы результирующий список был как можно более «сбалансированным» или «равномерно распределенным» (в кавычках, потому что я не уверен, что это лучший способ описать его ... позже я предоставлю способ измерить, если результат лучше, чем другие)....

Я изучил кое-что о сложности Колмогорова , прочитал некоторые статьи и книги Витани и Ли и использовал концепцию нормализованного расстояния сжатия для проверки стилометрии авторов (определите, как каждый автор пишет некоторые текстовые и групповые документы по их сходству). В этом случае...

Я хотел бы начать с вопроса, говоря, что я программист, и у меня нет большого опыта в теории сложности. Одна вещь, которую я заметил, состоит в том, что, хотя многие проблемы являются NP-полными, когда они распространяются на проблемы оптимизации, некоторые из них гораздо сложнее приблизить, чем...

У меня NP-полное решение проблемы. Учитывая пример проблемы, я хотел бы разработать алгоритм, который выводит ДА, если проблема выполнима, и НЕТ, в противном случае. (Конечно, если алгоритм не является оптимальным, он будет делать ошибки.) Я не могу найти никаких приближенных алгоритмов для таких...

Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами. Решение проблемы является NP-полным даже для бинарных деревьев. Результаты сложности для минимизации...

Я просматривал этот сайт, и там говорится, что люди нашли решения для туров TSP, которые на 0,031% выше, чем оптимальный тур. Не найдя оптимального тура, откуда они знают, какой длины он должен...

Из того, что я прочитал в preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D. Это определение PTAS : Схема аппроксимации полиномиального времени ( PTAS ) для задачи - это...

Учитывая тот факт , что - путь перечисления является # Р-полной задачи, может ли быть эффективные методы , которые вычисляют (или , по меньшей мере , приблизительно) средняя длина - пути без перечисления их? Что если пути разрешены для пересмотра вершин?т с тsssTTtsssTTt Соответствующие результаты...

Согласно статье в Википедии о схемах аппроксимации за полиномиальное время : Все проблемы в FPTAS доступны для фиксированных параметров. Этот результат меня удивляет - эти занятия, похоже, совершенно не похожи друг на друга. FPTAS характеризует проблемы по тому, насколько легко их аппроксимировать,...

Что такое алгоритм bicriteria приближение? Это продолжает прибывать в случае потока данных кластеризации. Это связано с многоцелевой оптимизацией? Именно там я наткнулся на него: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. Статья посвящена потоковой версии алгоритма k-средних. В статье есть...

Пусть будет некоторой проблемой подсчета, которая известна как # P -Complete .ΠΠ\PiPPP Означает ли это , что является P X -Жесткий (т.е. не PTAS для проблема существует , если P = N P...

Проблема заключается в следующем: У нас есть двумерный массив / сетка чисел, каждое из которых представляет некоторую «выгоду» или «прибыль». У нас также есть два фиксированных целых числа и h (для «ширины» и «высоты».) И фиксированного целого числа n .wwwhhhnnn Теперь мы хотим наложить...

Пусть - довольно приятная функция (например, непрерывная, дифференцируемая, не слишком много локальных максимумов, может быть вогнутая и т. Д.). Я хочу найти максимумы : значение которое делает максимально большим.f:Rd→Rf:Rd→Rf:\mathbb{R}^d \to \mathbb{R}fffx∈Rdx∈Rdx \in \mathbb{R}^df(x)f(x)f(x)...

Пусть будет языком всех -CNF-формул таким образом, чтобы по крайней мере из предложений можно было выполнить.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Мне нужно доказать, что существует st is -hard для любого...

Дана (двоичная) целочисленная программа вида:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Обратите внимание, что размер не...