Сглаженный анализ был применен много раз, чтобы понять время выполнения точных алгоритмов для многих задач, таких как линейное программирование и k-средних. В этой области есть довольно общие результаты, например, Хейко Рёглин и Бертольд Вёкинг, Сглаженный анализ целочисленного программирования ,...
Какая связь между PLSPLS\mathsf{PLS} и APXAPX\mathsf{APX} ? Другими словами, аппроксимируются ли задачи, допускающие локальный поиск за полиномиальное время? Означают ли приближенные задачи оптимизации алгоритм локального поиска...
Input вселенная и семейство подмножеств , скажем, . Будем считать , что подмножества можно покрыть , то есть, .U F ⊆ 2 U F U ⋃ E ∈ F E = UUUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Инкрементный последовательность покрытие представляет собой...
Какие проблемы с наилучшим известным коэффициентом аппроксимации достигаются алгоритмом, возвращающим равномерно случайное решение? Я знаю один такой пример для задачи магазина перестановок : в статье « Тесные границы для планирования потока перестановок » Вишванат Нагараджан и Максим Свириденко...
Я ищу имя или какие-либо ссылки на эту проблему. Для заданного взвешенного графа найти разбиение вершин с точностью доустанавливает таким образом, чтобы максимизировать значение срезов: Обратите внимание, что некоторые из множеств могут быть пустыми. Таким образом, проблема, по сути, заключается в...
В моей работе возникает следующая проблема: Существует ли известный алгоритм, который аппроксимирует хроматическое число графа без независимого набора порядка 65? (Таким образом, альфа (G) <= 64 известна, а | V | / 64 - тривиальная нижняя, | V | тривиальная верхняя граница. Но существуют ли...
Поскольку 2 NP-полные задачи по определению сводимы друг к другу, поэтому решение одной из них можно получить с помощью черного ящика, решающего другую, почему они не имеют сходных отношений аппроксимации (ссылаясь на их аналоги по оптимизации )? Я предполагаю, что некоторый постоянный или даже...
Я был бы очень заинтересован ссылками на теорию субмодулярных функций (от основ до продвинутых). В частности, я изучаю приближения к сложным задачам оптимизации и хочу развить свои основы субмодулярных функций, поскольку они имеют отношение к задачам оптимизации, которые я изучал. Заранее...
Была ли эта проблема изучена раньше? Учитывая метрический неориентированный граф G (длины ребер удовлетворяют неравенству треугольника), найдите множество S вершин, таких что MST (G [S]) максимизировано, где MST (G [S]) - минимальное остовное дерево подграфа, индуцированное С. Была ли эта проблема...
У меня есть несколько миллионов 32-битных значений. Для каждого значения я хочу найти все другие значения в пределах расстояния Хэмминга, равного 5. В наивном подходе это требует сравнений, которых я хочу избежать.O ( N2)O(N2)O(N^2) Я понял, что если я просто обработал эти 32-битные значения как...
В ориентированном графе , , если - DAG (направленный ациклический граф), называется множеством дуг обратной связи. F ⊂ E G ∖ F FG = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Если каждое ребро связано с весом , минимальная проблема набора дуги обратной связи по стоимости состоит...
Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может...
Алгоритмы аппроксимации могут давать результат до некоторого постоянного фактора. Это немного менее удовлетворительно, чем точные алгоритмы. Однако постоянные факторы игнорируются во временной сложности. Поэтому мне интересно, возможен ли или был использован следующий прием для решения некоторой...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Есть и другие показатели качества:...
Нам дают матроида. Наша цель - найти набор элементов минимального размера, который имеет непустое пересечение с каждой базой матроида. Проблема изучалась раньше? Это в P? Например, в матроиде остовного дерева минимальный набор попаданий должен быть минимальным срезом....
Я знаком с алгоритмом градиентного спуска, который может найти локальный минимум (максимум) данной функции. Есть ли какая-либо модификация градиентного спуска, которая позволяет найти абсолютный минимум (максимум), где функция имеет несколько локальных экстремумов? Существуют ли общие методы, как...
У меня есть вопрос о целесообразности, который можно сформулировать следующим образом. Мне дана точка в d- мерном векторном пространстве, и я хочу найти ближайшую точку q к p, которая удовлетворяет набору « ℓ 0 ограничений» видаpppdddqqqpppℓ0ℓ0\ell_0 Для данного множества не более одного из { q j ,...
Кажется, есть много рандомизированных алгоритмов для проверки полиномиальной идентичности, проверяя, равен ли данный полином нулю. Есть ли какие-либо результаты алгоритмов, которые делают своего рода оценку полиномов по определенному набору точек? Это может быть, например, аппроксимация, для какой...
Теорема Борсука-Улама говорит, что для любой непрерывной нечетной функции из n-сферы в евклидово n-пространство существует точка такая, что .х 0 г ( х 0 ) = 0гggИкс0x0x_0г( х0) = 0g(x0)=0g(x_0)=0 Simmons и Su (2002) описывают метод аппроксимации точки с использованием леммы Такера . Однако не ясно,...
Рассмотрим проблему доминирующего множества в общих графах, и пусть будет количеством вершин в графе. Алгоритм жадного приближения дает гарантию приближения фактора , т. Е. В полиномиальное время можно найти решение такое, что , где - размер минимального доминирующего множества. Есть оценки ,...