Open Classic Hard Problems

Материал из DISCOPAL
Перейти к: навигация, поиск

Всего страниц найдено: 210.

Задача «Minimum Multiprocessor Scheduling»©

  • Набор задач T, m процессоров, время выполнения K_n.
  • Найти m-процессорное расписание для T, т.е. функцию K_4.
  • Минимизировать время выполнения расписания, т.е. 
\binom{n}{4} 2^{-5}

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: JulesIMF 15:31, 28 мая 2023 (UTC)

Задача «Minimum K-Satisfiability»©

  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Abel1502 09:57, 25 мая 2023 (UTC)

Задача «Minimum Exact Cover»©

Minimum-exact-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать суммарных объем покрывающих подмножеств, т.е. K_4

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Анна Савчук 12:55, 25 апреля 2023 (UTC)

Задача «Maximum K-Satisfiability»©

  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Максимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.
  • Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.

Задача зарезервирована: Abel1502 08:50, 11 мая 2023 (UTC)

Задача «[[Open Exercises|]]»©

Всего страниц найдено: 72.

Задача «Задачи/eupce-1-11-a»©

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо

может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита: 

   \max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t,i) → min

Задача «Задачи/eupce-6-2-a»©

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа \sum_{(x,y,w) ∈ A}c(x,y,w) → \min в два цвета, такое что полное число одноцветных подграфов \sum\limits_{c\in C'} |c| → \min будете не больше чем d(c_i,c_j)∈ N

Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)

Задача «Задачи/eupce-6-20»©

Бонусная задача

Eupce-6-20 2023-05-19 12-27-59 image0.png

Задача «Задачи/eupce-6-19»©

Бонусная задача

Eupce-6-19 2023-05-19 12-22-45 image0.png Eupce-6-19 2023-05-19 12-23-03 image0.png

Задача «Задачи/eupce-6-17»©

Бонусная задача

Eupce-6-17 2023-05-18 19-57-47 image0.png

Задача «Задачи/eupce-6-15»©

Бонусная задача

Eupce-6-15 2023-05-18 19-51-41 image0.png

Задача «Задачи/eupce-6-14»©

Бонусная задача

Eupce-6-14 2023-05-18 19-44-29 image0.png

Задача «Задачи/eupce-6-13»©

Бонусная задача

Eupce-6-13 2023-05-18 19-43-15 image0.png

Задача «Задачи/eupce-6-11»©

Бонусная задача

Eupce-6-11 2023-05-18 19-41-29 image0.png

Задача «Задачи/eupce-6-10»©

Бонусная задача

Eupce-6-10 2023-05-18 19-38-29 image0.png Eupce-6-10 2023-05-18 19-38-53 image0.png

Задача «Задачи/eupce-6-9»©

Бонусная задача
Eupce-6-9 2023-05-18 19-35-59 image0.png

Задача «Задачи/eupce-6-8»©

Бонусная задача

Eupce-6-8 2023-05-18 19-34-01 image0.png

Задача «Задачи/eupce-6-7»©

Бонусная задача

Eupce-6-7 2023-05-18 19-27-32 image0.png

Задача «Задачи/eupce-6-4»©

Бонусная задача

Eupce-6-4 2023-05-18 19-16-39 image0.png

Задача «Задачи/eupce-6-3-b»©

Бонусная задача
  • Дан n-вершинный неориентированный граф G=(V, E)

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.

Предложите вероятностный алгоритм для поиска σ

для которого можно показать, что ожидаемый размер

где означает степень вершины i.

Докажите, что в G существует независимое множество размера как минимум

Задача «Задачи/eupce-6-3-a»©

  • Дан n-вершинный неориентированный граф G=(V, E)

Рассмотрим следующий метод генерации независимого множества.

Для заданной перестановки вершин σ, определим подмножество S(σ) вершин следующим образом: для каждой вершины i, i ∈ S(σ) тогда и только тогда, когда никакой ни один сосед j вершины i не предшествует i в перестановке σ.

Покажите, что каждый S(σ) будет независимым множеством в G.

Задача «Задачи/eupce-6-1-b»©

Предложите алгоритм дерандомизации методом условных вероятностей для алгоритма из MAX-SAT: вероятностное округление/Задачи/eupce-6-1-a‎.

Задача «Задачи/eupce-6-1-a»©

Рассмотрим K-ESAT, SAT, когда в каждой скобке ровно k литералов.

Предложите Лас-Вегас алгоритм выполняющий минимум

скобок, и проанализируйте матожидание его времени выполнения.

Задача «Задачи/eupce-2-13-b»©

Решите обобщенную версию задачи [[../eupce-2-13]]:

  • kn различных купонов, организованных в n непересекающихся наборов из k купонов.
  • нужен один купон из каждого набора.

Задача «Задачи/eupce-2-13»©

  • Каждая коробка хлопьев содержит один из 2n различных купонов (купон в каждой коробке выбирается независимо и равномерно случайным образом из 2n).
  • Купоны организованы в n пар, так что купоны 1 и 2 составляют пару, купоны 3 и 4 составляют пару и так далее.
  • Получив по одному купону из каждой пары, вы можете получить приз.

Какое ожидаемое количество коробок, надо для этого купить?

Задача «Задачи/eupce-2-9»©

Дважды бросают честный k-гранный кубик с числами от 1 от k до k на гранях кубика, получая значения X1 и X2.

  • E[max(X1, X2)] = ?
  • E[min(X1, X2)] = ?

Покажите, что E[max(X1 , X2)] + E[min(X1 , X2)] = E[X1] + E[X2].

Задача «Задачи/eupce-2-8-a»©

Алиса и Боб решили заводить детей до тех пор, пока у них не родится девочка или пока у них не будет k ≥ 1 детей.

Предположим, что каждый ребенок будет мальчиком или девочкой независимо с вероятностью 1/2 и что многоплодных родов не бывает.

  • Каково ожидаемое число детей женского пола?
  • Каково ожидаемое число детей мужского пола?

Задача «Задачи/eupce-2-7-d»©

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

E[X | X ≤ Y] = ?

Задача «Задачи/eupce-2-7-c»©

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

P(min(X, Y) = k) = ?

Задача «Задачи/eupce-2-7-b»©

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

E[max(X, Y)] = ?

Задача «Задачи/eupce-2-7-a»©

X и Y — независимые случайные величины с геометрическим распределением, с параметрами P и Q соответственно.

P(X = Y) = ?

Задача «Задачи/eupce-2-6-d»©

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

  • 2 ≤ k ≤ 12
  • E[X1 - X2 | X = k] = ?

Задача «Задачи/eupce-2-6-c»©

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

E[X1 | X = 9] = ?

Задача «Задачи/eupce-2-6-b»©

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

E[X | X1 = X2] = ?

Задача «Задачи/eupce-2-6-a»©

Предположим, что независимо бросают два стандартных шестисторонних кости, X1 — то, что выпадает на первой, X2 — на второй, а X — сумма обоих значений.

E[X | X1 — четное] = ?

Задача «Задачи/eupce-2-5»©

Если X — случайная величина с биномиальным распределением B(n, 1/2) для n ≥ 1, покажите, что вероятность того,

что X — четное будет 1/2.

Задача «Задачи/eupce-2-4»©

Докажите, что для любого целого .

Задача «Задачи/eupce-1-26-b»©

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

  • Как обычно, крестики и нолики ходят по очереди и нолик идет первым. Как обычно, выигрывает тот, кто первый добъется «три в ряд», или ничья, если никто.
  • Но на каждом ходе позиция и у крестиков и у ноликов выбирается независимо и равномерно среди свободных квадратов.

Найдите вероятность, выигрыша для «крестиков» и для «ноликов».

Задача «Задачи/eupce-1-26-a»©

Обычные крестики-нолики скучные, при оптимальной стратегии в них выигрывают крестики.

Рассмотрим вероятную модификацию этой игры.

  • Изначально, бросая честную монетку, разметим каждый из девяти квадратов либо X, либо O.
  • Если только один из игроков имеет «три в ряд» → он победил.
  • Если оба или никто → ничья.

Определите вероятность, что «X» выиграет.

Задача «Задачи/eupce-1-18»©

  • Есть функция
  • и известно что .

Единственный способ вычисления F — использовать таблицу поиска, в которой хранится значения F. К сожалению, злой противник изменил значение 1/5 записей в этой таблице.

Опишите простой рандомизированный алгоритм, который, учитывая входной Z, выводит значение, которое равняется f(z) с вероятностью не менее 1/2.

Ваш алгоритм должен работать для каждого значения Z, независимо от того, какие записи изменил противник.

Дополнительно, предположим, вам разрешено повторить этот ваш начальный алгоритм три раза.

Как этим воспрользоваться, чтобы максимально увеличить вероятность правильного ответа, и какова эта вероятность?

Задача «Задачи/eupce-1-16-d»©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

  • Игрок начинает с броска всех трех кубиков.
  • После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
  • После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

  • если все три кости одинаковые → останавливаемся и выигрываем;
  • если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
  • если все не совпадают — перебрасываем их всех.

Рассматривая все возможные возможные выпадения костей, найдите вероятность того, что игрок выиграет.

Задача «Задачи/eupce-1-16-c»©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

  • Игрок начинает с броска всех трех кубиков.
  • После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
  • После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

  • если все три кости одинаковые → останавливаемся и выигрываем;
  • если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
  • если все не совпадают — перебрасываем их всех.

Найдите вероятность того, что игрок выиграет, если на первом шаге он уже выбросил две одинаковые кости.

Задача «Задачи/eupce-1-16-b»©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

  • Игрок начинает с броска всех трех кубиков.
  • После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
  • После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

  • если все три кости одинаковые → останавливаемся и выигрываем;
  • если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
  • если все не совпадают — перебрасываем их всех.

Найдите вероятность того, что ровно два из трех кубиков показывают одинаковое число в первом броске.

Задача «Задачи/eupce-1-16-a»©

Рассмотрим игру, основанную на бросках трех стандартных шестисторонних костей.

Цель → получить одинаковое число на всех трех костях, кто первый этого добьется, тот выиграл.

  • Игрок начинает с броска всех трех кубиков.
  • После первого броска игрок может выбрать одну, две или три кости и бросить их снова.
  • После второго броска игрок один из трех кубиков и перебросить его.

Предположим, что игрок использует следующую оптимальную стратегию:

  • если все три кости одинаковые → останавливаемся и выигрываем;
  • если два кубика совпадают, игрок перебрасывает тот, который «выбивается из коллектива».
  • если все не совпадают — перебрасываем их всех.

Найдите вероятность того, что все три кубика показывают одинаковое число в первом броске.

Задача «Задачи/eupce-1-15»©

Предположим, что бросают десять стандартных шестисторонних костей.

Какова вероятность того, что их сумма будет деленной на 6, предполагая, что броски независимы?

Задача «Задачи/eupce-1-14»©

Я играю в турнире ракетбола против игрока, против которого раньше не играл, но видел его в игре.

Априори рассматриваю три равновероятные возможности:

  • мы одинаково талантливы, каждый из нас в равной степени может выиграть каждую игру;
  • Я немного лучше, и поэтому я выигрываю каждую игру независимо с вероятностью 0.6;
  • Он немного лучше, и поэтому он выигрывает каждую игру независимо с вероятностью 0.6.

В рокетбол играют, пока один игрок не выиграет три сета. В нашей игре, я выиграл только второй сет, а противник выиграл первый, третий и четвертый.

В апостеорной модели, с какой вероятностью я должен верить, что мой оппонент немного лучше, чем я?

Задача «Задачи/eupce-1-13»©

Медицинская компания рекламирует свой новый тест на определенное заболевание.

Частота ошибок первого рода (false negative) мала: если у вас есть расстройство, вероятность того, что тест вернет положительный результат, составляет 0.999.

Частота ошибок второго рода (false positive) тоже невелика: если у вас нет расстройства, вероятность того, что тест вернет положительный результат, составляет всего 0.005.

Предположим, что эту болезнь имеет 2% населения.

Если мы проверяем человека, выбранного равномерно из популяции, и получается положительный результат, какова вероятность того, что эта болезнь у него действительно есть?

Задача «Задачи/eupce-1-12»©

Есть три коробки.

В одной миллион рублей, в двух других — 100р.

Игра играется следующим образом:

  • Участник выбирает коробку.
  • Ведущий открывает одну из других коробок, чтобы убедить, что там всего — 100р.
  • Участник может выбрать первоначально выбранную коробку или переключится на другую (разумеется, логично выбрать не ту, где показали 100 р).

Итак, если участник сменит выбранную на первом шаге коробку, увеличит ли это его шансы?

Задача «Задачи/eupce-1-11-b»©

  • Пытаемся передать один бит (0 или 1) через промежуточные узлы, каждый из которых независимо может инвертировать бит с вероятностью «p».
  • Скажем, узел имеет смещение «q», если это , «смещение» будет вещественным числом на отрезке [−1, 1].

Докажите, что прохождение бита через узлы со смещениями «q1» и «q2» эквивалентно прохождению бита через один узел со смещением «q1×q2».

Задача «Задачи/eupce-1-11-c»©

Пытаемся передать один бит (0 или 1) через «n» промежуточных узлов, каждый из которых независимо

может инвертировать бит с вероятностью «p».

Докажите, что вероятность получения корректного бита:

Задача «Задачи/eupce-1-10»©

Есть нормальная честная монета и фальшивая, с двумя «решками». Допустим, что мы

    • выбираем одну из двух монет случайным образом,
    • подбрасываем ее
    • выпала решка.

Какова вероятность, что мы выбрали фальшивую монету?

Задача «Задачи/eupce-1-9»©

  • Честную монету бросили «n» раз.
  • Для k>0, найдите верхнюю границу вероятности, что будет последовательность из последовательных орлов.

Задача «Задачи/P^BPP»©

Какой класс будет

Задача «Задачи/\Sigma^p k=NP^(\Sigma^p (k-1))»©

Докажите

Задача «Задачи/compliment-in-ph»©

Задача «Задачи/Свойство Sigma i=PH»©

.

Задача «Задачи/3csat-npc»©

Задача «Задачи/DHAM3»©

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делиться на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Докажите, что и — NP-трудны.

Задача «Задачи/MAX-CUT-NPC»©

Докажите, что задача MAX-CUT, в форме задачи разрешения («правда, ли, что для графа G есть разрез больше K?») NP-полна.

Задача «Задачи/NTIME-NlogN-reduction-3SAT»©

Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .

Задача «Задачи/QBEQ-NPC-NPC»©

Покажите NP-полноту языка совместимых систем квадратичных уравнений в булевых переменных. Т.е. разрешимых систем вида

и где сложение по модулю 2.

Задача «Задачи/USUBSETSUM-IN-P»©

Вспомним задачу булев-рюкзак выполнимость, и потребуем, чтобы все веса и размер рюкзака задавались в унарной системе ().

Покажите, что тогда язык таких выполнимых рюкзаков, лежит в классе P.

Задача «Задачи/accept-after-t-steps-in-npc»©

Язык L состоит из пар (M, t), где

M
одноленточная машина Тьюринга над бинарным алфавитом.
t
число t единичной системе (t единиц).
  • Существует вход x, M(x) останавливается и возвращает 1, после t шагов.

Покажите, что это NP-полная задача.

Задача «Задачи/conp-as-yes»©

Покажите, что язык L лежит в co-NP тогда и только тогда, если существует недетерминированная машина M, и полином p, такой, что M останавливается за время p(n) для всех входов x длины n, и L состоит точно только из таких строк x, у которых все пути вычисления M(x) приводят к ответу «1».

Задача «Задачи/scheduling-ident-machines-in-npc»©

Рассмотрим задачу разрешения для оптимизационной задачи Планирование Задач на Одинаковых Машинах («если ли планировка с максимальным временем меньше k»).

Покажите, что эта задача, даже в случае p=2, NP-полна.

Задача «Задачи/unary-in-p-then-exptime-nexp»©

Докажите, что если каждый унарный язык из NP также лежит в P, то EXPTIME=NEXP.

Задача «Задачи/unary-in-p-then-time2kn-in-time2cn»©

Докажите, что если каждый унарный язык из NP также лежит в P, то то для любого языка из для какого-либо k, он тажке лежит в для любого c.

Задача «Задачи/Квадрат букв»©

Задача «Задачи/Порядок закачек — NPC»©

Представим распределенный сервис стриминга видеофильмов. Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.

Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.

Конкретно, узел контроля планирования получает n-заданий вида:

  • «начать_не_раньше, закончить_не_позже, размер_фильма»i, 1<=i<=n
  • максимальная пропускная способность не больше МаксКанал

И говорит «OK» (или «Паника-Паника!» в противном случае), если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n ):

  • «время_начала, время_окончания, ширина_канала»i,
  • время_началаi >= начать_не_раньшеi
  • время окончанияi <= закончить_не_позжеi
  • ширина_каналаi <= МаксКанал
  • ширина_канала*(время_окончания — время_начала)i >= размер_фильмаi

Докажите NP-полноту задачи.

Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM»

Задача «Задачи/ptas-for-minimal-scheduling»©

Разработайте PTAS-алгоритм для Планирование Задач на Одинаковых Машинах используя этот подход.

Задача «Задачи/NP-sums»©

Проверить принадлежность классу следующей задачи: по заданному конечному множеству натуральных чисел, представленных в своей бинарной записи, определить возможность разделения этого множества на два подмножества с одинаковыми суммами.

Задача «Задачи/dtime-n2-is-closed-carp-reduction»©

  • Класс сложности С замкнут относительно какой-то сводимости, если L→L' и , то .

Рассмотрим класс .

Замкнут ли он относительно полиномиальной сводимости по Карпу?

Задача «Задачи/maximum-k-choice-knapsack-dynamic-programming»©

Придумайте алгоритм динамического программирования, находящий оптимальное решение задачи Maximum Integer k-choice Knapsack.

Задача «Задачи/Жадное вершинное покрытие для почти всех исходных данных»©

Рассмотрим жадный алгоритм для вершинного покрытия («брать вершину максимальной степени, ребра удалять»), на случайных графах, у которых

  • n-вершин
  • ребра между любой парой вершин возникают с вероятностью p.

Какова точность алгоритма для почти всех исходных данных?

(упрощенный вариант — для фиксированного p=½).

Задача «Задачи/P^(\Sigma^p k)=P^(\Pi^p k)»©

Докажите

Задача «[[Open Classic Hard Problems|]]»©


Задача «[[Зарезервированные практические задачи|]]»©

Всего страниц найдено: 12.

----

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа K_n в два цвета, такое что полное число одноцветных подграфов K_4 будете не больше чем \binom{n}{4} 2^{-5}

Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=Теоретические_задачи notcategory=Solved notcategory=Решенные_задачи ignore=Permission denied ignore=A ignore=Open_Exercises ignore=Открытые_теоретические_задачи


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Abel1502 09:57, 25 мая 2023 (UTC)


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Максимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.
  • Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.

Задача зарезервирована: Abel1502 08:50, 11 мая 2023 (UTC)


  • Набор задач T, m процессоров, время выполнения l(t,i)∈ Z^+, \ \ ∀t∈ T, \ i∈ [1..m].
  • Найти m-процессорное расписание для T, т.е. функцию f: T→ [1..m].
  • Минимизировать время выполнения расписания, т.е. 
\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t,i) → min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: JulesIMF 15:31, 28 мая 2023 (UTC)


  • Три множества X, Y, W и функция стоимости c: X×Y×W → N
  • Найти назначение A, т.е. подмножество A ⊆ X×Y×W, такой что каждый элемент из X ∪ Y ∪ W принадлежит только одной тройке из A.
  • Минимизировать стоимость назначения, т.е.

\sum_{(x,y,w) ∈ A}c(x,y,w) → \min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Krym4s 15:55, 9 мая 2023 (UTC)

Minimum-exact-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать суммарных объем покрывающих подмножеств, т.е. \sum\limits_{c\in C'} |c| → \min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Анна Савчук 12:55, 25 апреля 2023 (UTC)

Maximum-set-splitting.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти разбиение S, на непересекающиеся множества S1 и S2.
  • Максимизировать число подмножеств C, которые «разделены» между S1 и S2, т.е. не лежат полностью в S1 или S2.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Ilya 16:25, 2 мая 2023 (UTC)


  • Набор C из m городов с заданными расстояниями между ними d(c_i,c_j)∈ N для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
  • Найти тур C, т.е. перестановка \pi: [1..m]→ [1..m].
  • Минимизировать длину этого тура

d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: StasFomin 21:17, 26 апреля 2023 (UTC)

Maximum-cut.png
  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача зарезервирована: Artklyachin 14:06, 18 мая 2023 (UTC)

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=ClassicHardProblems notcategory=Solved ignore=Permission denied ignore=A ignore=Open Classic Hard Problems


Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (5) лет при минимально возможных затратах.

Период планирования; 5 лет

Потребность в электроэнергии описывается кривой продолжительности нагрузки (LDC), как показано на рис (цифры на картинке приблизительны, точные будут дальше текстом), по оси ординат — мегаватты, по оси абсцисс — часы.

Планируем генерацию электричества 2022-10-21 16-20-36 image0.png

Площадь под графиком соответствует потребностям производства электроэнергии в мегаватт-часах.

Чтобы модель была простой, например линейной, график аппроксимируется кусочно-постоянной функцией, показанной в виде гистограммы (ступенчатой функции), с

  • «Bars=4».
  • TD — отсечки по горизонтали 
 2920 3650 1280 910

Первый столбец обозначает минимальную нагрузку, столбец «4» — пиковую нагрузку, а два промежуточных — представляют потребность в средней нагрузке.

В любой компании или стране для производства электроэнергии используется несколько различных типов (n=5) технологий, таких как

  • паровые турбины
  • газовые турбины
  • гидроэлектростанции
  • дизель-генераторы
  • комбинированные генераторы

Эти энергоблоки требуют различных затрат, затрат на установку и переменных затрат, и переменная по времени генерации (что-то ломается, что-то амортизируется, что-то улучшается).

CE_{it}, 1 \leq i \leq n; — планируемые мощности существующих генерирующих типов по времени.
    15000 18000  20000  21000  21000
    40000 350000 300000 280000 280000 
    50000 400000 400000 400000 300000
    10000 100000 120000 130000 150000
     1000  11000 12000  14000  16000
VC_{it}; Переменная (на мегаватт) годовая стоимость старой установки типа «i»
    4 4 4 4 4
    5 5 5 5 5
    3 3 3 3 3
    3 3 3 3 3
    1 1 1 1 1

Кроме того, в будущем могут быть добавлены дополнительные мощности.

Например, предположим, что модель решила установить новую установку типа «j=1» мощностью 50 МВт в период «1», она будет существовать в системе до истечения технического срока службы этой установки (Это потому, что продолжительность горизонта планирования, рассматриваемого в этой задаче, короче, чем технический срок службы любого нового энергоблока, доступного на рынке).

FC_{jt}; Фиксированная годовая стоимость новой установки типа «j»
    100 110 110 120 120
    200 200 200 200 200 
    300 290 290 285 285
    200 190 190 180 180
    50 50 50 50 50  ~
FC_{jt}; Фиксированная годовая стоимость новой установки типа «j»


!AF; 80 80 85 85 85 

    85 85 85 85 85
    90 90 90 90 90
    90 90 95 95 95
    85 85 90 90 90~

!PD; 6000 6000 6000 6000 6000 

    9000 10000 110000 12000 13000
    25000 27000 27000 27000 27000
    50000 58000 58000 58000 57000~

!W; 20 50 10 10 10~







Кроме того, они имеют разный технический срок службы и придерживаются разных правил технического обслуживания.

Задача планирования состоит в том, чтобы определить

  • график работы существующих установок,
  • установок нового поколения, которые будут запущены в будущем,
  • и график введения новых установок путем минимизации суммы затрат на установку и эксплуатацию за заданное количество

лет, соблюдая при этом технические и финансовые ограничения.

Как только будет добавлен новый энергоблок с заданной мощностью, этот энергоблок будет эксплуатироваться на протяжении всего горизонта планирования.


С другой стороны, администрация имеет предпочтение между различными типами технологий, то есть между различными генерирующими установками в случае новых установок.

Это предпочтение описывается процентным коэффициентом от минимума, который должен иметь каждый новый блок, по сравнению с общей энергией, установленной в новых блоках.


Пока не додумано, надо доработать

Задача зарезервирована: StasFomin 16:33, 27 ноября 2022 (UTC)

Задача «Maximum Cut»©

Maximum-cut.png
  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача зарезервирована: Artklyachin 14:06, 18 мая 2023 (UTC)

Задача «Minimum Traveling Salesperson»©

  • Набор C из m городов с заданными расстояниями между ними для каждой пары городов.
  • Найти тур C, т.е. перестановка .
  • Минимизировать длину этого тура

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum 3-Dimensional Assignment»©

  • Три множества X, Y, W и функция стоимости c: X×Y×W → N
  • Найти назначение A, т.е. подмножество A ⊆ X×Y×W, такой что каждый элемент из принадлежит только одной тройке из A.
  • Минимизировать стоимость назначения, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Krym4s 15:55, 9 мая 2023 (UTC)

Задача «Maximum Set Splitting»©

Maximum-set-splitting.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти разбиение S, на непересекающиеся множества S1 и S2.
  • Максимизировать число подмножеств C, которые «разделены» между S1 и S2, т.е. не лежат полностью в S1 или S2.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Ilya 16:25, 2 мая 2023 (UTC)

Задача «Maximum Class-Constrained Knapsack»©

  • n размеров заданных вектором , m рюкзаков разных размеров и числом отсеков заданных векторами , причем .
  • Найти размещение заданных элементов в эти рюкзаки, заданный двумя n×m матрицами,

, такой, что

  • Максимизировать число упакованных элементов 
.


Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Integer K-Choice Knapsack»©

  • Неотрицательные целочисленные m×k матрицы , неотрицательное целое b∈ N.
  • Найти
    • неотрицательный целочисленный n-вектор ,
    • функция
    • такие, что .
  • Максимизировать 
.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Maximum Knapsack»©

Maximum-knapsack.png
  • Конечное множество U, для каждого u ∈ U задан
    • вес-размер
    • ценность
  • Положительное целое — размер рюкзака.
  • Выбрать подмножество U' ⊆ U, не превышающее емкость рюкзака:
  • Максимизировать ценность выбранных элементов, .


Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Maximum Integer M-Dimensional Knapsack»©

  • Неотрицательная целочисленная m×n матрица
    • неотрицательный целочисленный вектор m-вектор .
  • Найти неотрицательный целочисленный n-вектор , такой что Ax≤b.
  • Максимизировать скалярное произведение c и x, т.е., .


Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Maximum Quadratic Programming»©

Maximum-quadratic-programming.png
  • Положительное целое n, набор линейных ограничений заданных в виде m×n матрицы, и m-вектора b, задающие область ограничениями .
  • многомерный многочлен f, максимальной степени не больше 2. Имея
    • Q — симметричная положительно-полуопределенная матрица,
    • c — вектор линейных коэффициентов
  • Можно представить его в виде:
  • Максимизировать значение f в области заданной линейными ограничениями, т.е. .

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача «Maximum Bounded 0-1 Programming»©

Maximum-bounded-0-1-programming.png
  • Целая m×n-матрица , целый m-вектор , неотрицательный бинарный -вектор .
  • Найти двоичный n-вектор , такой что Ax ≤ b.
  • Максимизировать скалярное произведение c и x, т.е., .

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Minimum Covering Integer Programming»©

Minimum-covering-integer-programming.png
  • Рациональная m×n-матрица , рациональный m-вектор , рациональный -вектор .
  • Найти рациональный n-вектор , такой что Ax≥b.
  • Минимизировать скалярное произведение c и x, т.е., .

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Minimum 0-1 Programming»©

Minimum-0-1-programming.png
  • Целая m×n-матрица , целый m-вектор , неотрицательный целый -вектор .
  • Найти двоичный n-вектор , такой что Ax≥b.
  • Минимизировать скалярное произведение c и x, т.е., .

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Maximum Packing Integer Programming»©

Maximum-packing-integer-programming.png
  • Рациональная m×n-матрица , рациональный m-вектор , рациональный -вектор .
  • Найти рациональный n-вектор , такой что Ax≤b.
  • Максимизировать скалярное произведение c и x, т.е., .

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.

Задача «Minimum Metric Traveling Salesperson Problem»©

  • Набор C из m городов с заданными расстояниями между ними для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
  • Найти тур C, т.е. перестановка .
  • Минимизировать длину этого тура

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: StasFomin 21:17, 26 апреля 2023 (UTC)

Задача «Minimum Upgrading Spanning Tree»©

  • Граф G=(V,E), три функции весов на ребрах (для всех e ∈ E), где означает вес ребра e, если i его концов «обновлены», причем известна стоимость обновления c(v) для каждой вершины v ∈ V, и некое ограничивающее значение D для веса минимального остовного дерева.
  • Найти набор обновляемых вершин W⊆V, так чтобы вес минимального остовного дерева с весами dW, была ограничена D.
    • dW означает вес ребра в результате обновления вершин в W, т.е. , где .
  • Минимизировать стоимость обновления вершин, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Set Packing»©

Maximum-set-packing.svg
  • Коллекция конечных множеств C.
  • Найти упаковку множеств, т.е. коллекцию непересекающихся множество C'⊆ C.
  • Максимизировать размер этой упаковки, т.е. |C'|

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum 3-Dimensional Matching»©

Maximum-3-dimensional-matching.svg
  • Множество T ⊆ X×Y×Z, с непересекающимися X, Y, и Z.
  • Найти трехмерное сопоставление для T, т.е. подмножество M⊆T, такое, что его элементы не пересекаются ни по одной координате.
  • Максимизировать размер сопоставления, т.е. |M| → max.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Set Cover»©

Minimum-set-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать число покрывающих подмножеств, т.е. |C'|→min.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum General Routing»©

  • Граф G=(V,E), длина l(e)∈ N на ребрах e ∈ E, подмножества E' ⊆ E, V'⊆V.
  • Цикл в G, который заходит ровно раз в каждую вершину из V' и пересекает каждое ребро из E'.
  • Минимизировать общую длину этого цикла.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Preemptive Scheduling With Set-Up Times»©

  • Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
  • Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач t1, …, tk, такое что
    • и есть некоторое назначение , которое назначает каждой подзадаче ti пару неотрицательных целых , таких, что
    • Это расписание должно удовлетворять дополнительному ограничению:
      • Если два подзадачи ti от t и tj' от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
        • — если у них один и тот же компилятор (c(t) = c(t'))
        • — если эти компиляторы разные.
  • Минимизировать общее время выполнения, т.е. максимум по всем подзадачам

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Cut Cover»©

Minimum-cut-cover.png

Граф G=(V,E).

Найти коллекцию разрезов V1, …, Vm,

т.е. коллекция подмножеств вершин , такая что каждое ребро графа (u,v)∈ E свои концы держит в разных подмножествах, т.е.

  • либо и
  • либо и

Минимизировать размер «m» этой коллекции.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача «Minimum K-Cut»©

Minimum-k-cut.png
  • Граф G=(V,E), веса на ребрах w: E → N, целое .
  • Найти разбиение V на k непересекающихся множеств .
  • Минимизировать сумму весов между ребрами, которые между этими множествами

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача «Maximum K-Cut»©

Maximum-k-cut.png
  • Граф G=(V,E), веса на ребрах w: E → N, целое .
  • Найти разбиение V на k непересекающихся множеств .
  • Максимизировать сумму весов между ребрами, которые между этими множествами

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача «Maximum Directed Cut»©

Maximum-directed-cut.png
  • Направленный граф G=(V,A).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число дуг, которые стартуют в V1, и заканчиваются в V2.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача «Minimum B-Balanced Cut»©

Minimum-b-balanced-cut.png
  • Граф G=(V,E), веса на вершинах w: V → N, стоимости на ребрах c: E → N, рациональное число b, .
  • Найти разрез C, т.е. подмножество вершин C⊆V, такой, что

, где where w(V') означает сумму весов вершин в V'.

  • Минимизировать вес разреза, т.е. 
,

где

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., 📹 видео 📹

Задача «Minimum Cut Linear Arrangement»©

  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию .
  • Минимизировать максимальное число ребер разреза в любой целой точке, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vertex K-Cut»©

  • Граф G=(V,E), набор , выделенных специальных вершин, веса для остальных вершин w: V-S → N, целое k.
  • Найти вершинный k-разрез, т.е. подмножество вершин , такое, что их удаление из графа отключает каждую специальную вершину si от ti для всех 1 ≤ i ≤ k.
  • Минимизировать сумму весов вершин в этом разрезе .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Induced Subgraph With Property P»©

  • Граф G=(V,E) и некое свойство (предикат) P над подграфами.
    • Свойство наследуемое, т.е. каждый подграф G' будет удовлетворять P, если сам G' ему удовлетворял.
    • Свойство нетривиальное, т.е. оно истинно и ложно для бесконечного количества графов.
  • Найти подмножество вершин V'⊆V, такое, что подграф порожденный V' имеет свойство P.
  • Максимизировать размер этого подграфа |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Register Sufficiency»©

  • Направленный ациклический граф G=(V,A)
  • Найти вычисление на G, которое использует k регистров, т.е.
    • порядок v1, …, vn на вершинах V
    • последовательность S0, …, Sn подмножеств V, удовлетворяющих
      • S0 — пустое
      • Sn — содержит все вершины с нулевой входящей степенью в G
      • 1 ≤ i ≤ n, , , и содержит все вершины u, для которых
  • Минимизировать число регистров,т.е. k.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Triangle Packing»©

  • Граф G=(V,E).
  • Найти «упаковку треугольников» для G, т.е. набор V1, V2, …, Vk непересекающихся подмножеств V,
    • каждое из которых содержит ровно три вершины — , 1 ≤ i ≤ k
    • и все три ребра , , есть в E.
  • Максимизировать размерность этой упаковки треугольников, т.е. число этих непересекающихся подмножеств Vi.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Edge Subgraph»©

  • Граф G=(V,E) с весами на ребрах w: E → N, положительное целое k.
  • Найти подмножество V'⊆V, заданного размера |V'|=k
  • Максимизировать общий вес ребер подграфа порожденного V',

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Domatic Partition»©

  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся наборы V1, V2, …, Vk такие, что каждый Vi доминирующее множество над G.
  • Максимизировать размерность разделения, т.е. число этих непересекающихся множеств вершин Vi.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Edge Connected Subgraph»©

  • Граф G=(V,E), константа k ≥ 2 .
  • Найти k-реберно-связный остовный подграф G'=(V,E'), т.е. остовный подграф, который нельзя сделать несвязным, удалив меньше чем k ребер.
  • Минимизировать размер остова , т.е. |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Vertex Connected Subgraph»©

  • Граф G=(V,E), константа k ≥ 2 .
  • Найти k-вершинно-связный остовный подграф G'=(V,E'), т.е. остовный подграф, который нельзя сделать несвязным, удалив меньше чем k вершин.
  • Минимизировать размер остова , т.е. |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Parallel Processor Total Flow Time»©

  • Набор задач T, m идентичных процессоров, каждая задача t ∈ T имеет время выпуска и длительность .
  • Найти m-процессорное расписание для T, удовлетворяющее ограничениям времени выпуска, т.е. функция f : T → N , такая что для всех u ≥ 0 и для любого процессора i, если S(u,i) это набор задач для которых и , то

и для каждой задачи t, .

  • Минимизировать полное время расписания, т.е.


Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Sum Of Squares»©

  • Конечное множество A, задан размер для каждого a ∈ A, и целое K ≥ 2 .
  • Найти разбиение A на множество из K непересекающихся множеств A1, A2, …, AK.
  • Минимизировать сумму квадратов их размеров

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Weighted Completion Time Scheduling»©

  • Набор задач T, m идентичных процессоров, каждая задача t ∈ T имеет
    • время выпуска
    • длительность .
    • вес .
  • Найти m-процессорное расписание для T, удовлетворяющее ограничениям времени выпуска, т.е. функция f : T → N , такая что для всех u ≥ 0 и для любого процессора i, если S(u,i) это набор задач для которых и , то

и для каждой задачи t, .

  • Минимизировать взешенную сумму времен выполнения, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Degree Bounded Connected Subgraph»©

  • Граф G=(V,E), вес на ребрах w : E → N и целое d ≥ 2
  • Найти подмножество ребер E' ⊆ E, такое что подграф G'=(V,E') связный и нет вершин степени большей d.

Максимизировать полный вес этого подграфа,

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Common Subgraph»©

  • Графы G1=(V1,E1) и G2=(V2,E2).
  • Найти общий подграф, т.е. подмножества E1' ⊆ E1 и E2' ⊆ E2, такие, что два подграфа и изоморфны.
  • Максимизировать размер общего подграфа, т.е. |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Common Induced Subgraph»©

  • Графы G1=(V1,E1) и G2=(V2,E2).
  • Найти общий порожденный подграф, т.е. подмножества V1' ⊆ V1 и V2' ⊆ V2, такие, что два подграфа G1', порожденный и G2', порожденный изоморфны.
  • Максимизировать размер общего подграфа, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Graph Transformation»©

  • Графы G1=(V1,E1) G2=(V2,E2).
  • Найти набор ребер E'⊆ E1, которых надо удалить из E1 и добавить в E2.
  • Минимизировать размер этого множества ребер, |E'|

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Separating Subdivision»©

  • Семейство непересекающихся полигонов P1, …, Pk.
  • Найти разделяющее подразделение, т.е. семейство из -полигонов R1, …, Rk, с попарно непересекающимися границами, такими, что для каждого , Pi ⊆ Ri.
  • Минимизировать размер подразделения, т.е. полное число ребер в полигонах R1, …, Rk.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Geometric Traveling Salesperson»©

  • Набор C ⊆ Z×Z из m точек на плоскости.
  • Тур C, т.е. перестановка .
  • Минимизировать длину тура где расстояние между точками (x1, y1) и (x2, y2) это округленная Евклидова длина

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Balanced Connected Partition»©

Связный граф G=(V,E) с неотрицательными весами на вершинах w: V → N.

Найти разбиение вершин V на непустые непересекающиеся множества (V1, V2), такие,

что подграфы порожденные V1 и V2 являются связными.

Минимизировать дисбаланс разбиения, т.е.

, где

Максимизировать размер этого разбиения.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Disjoint Connecting Paths»©

  • Мультиграф G=(V,E), коллекция пар вершин .
  • Найти коллекцию непересекающихся по ребрам путей в G соединающих некоторые из пар (si, ti), т.е. путь это последовательность вершин u1, u2, …, um, такая что для некоторого i, , и для всех j, .
  • Максимизация числа пар вершин (si, ti), которые будут соединены этими путями.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Integral K-Multicommodity Flow On Trees»©

  • Дерево T=(V,E), пропускная способность на ребрах c: E → N, k пар вершин (si, ti).
  • Найти поток , для каждой пары (si, ti), такой что , где , если e лежит на (единственном, тут дерево) пути из si в ti, и 0 в противном случае.
  • Максимизировать сумму потоков

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Achromatic Number»©

Граф G=(V,E).

Найти полную раскраску G, т.е. разбиение V на непересекающиеся наборы V1, V2, …, Vk, такие, что каждый Vi

  • независимое множество в G,
  • для каждой пары этих непересекающихся множеств Vi, Vj, Vi ∪ Vj не является независимым множеством.

Максимизировать размерность раскраски, т.е. число этих независимых наборов Vi.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum B-Vertex Separator»©

  • Граф G=(V,E), рациональное b, .
  • Найти разбиение V на непересекающиеся множества A, B, и C, такие что , и ни одно ребро не лежит разными концами в A и B одновременно.
  • Минимизировать размер разделителя, т.е. |C|.

Задача в лаб17 (рид-онли просмотр)

Задача «Shortest Common Supersequence»©

  • Конечный алфавит Σ, конечный набор R строк из .
  • Найти строку , такую что каждая строка x ∈ R является ее подпоследовательностью, т.е. можно получить x вычеркиванием символов из w.
  • Минимизировать длину этой суперпоследовательности |w|.

Задача в лаб17 (рид-онли просмотр)

Задача «Shortest Common Superstring»©

  • Конечный алфавит Σ, конечный набор R строк из .
  • Найти строку , такую что каждая строка x ∈ R является ее подстрокой, т.е. , для каких-то .
  • Минимизировать длину этой суперстроки |w|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Edge Coloring»©

Граф G=(V,E).

Найти полную раскраску ребер E, т.е. разбиение E на непересекающиеся наборы

E1, E2, …, Ek, такие, что

  • никакие два ребра из Ei не имеют общей вершины из G.

Минимизировать размерность раскраски, т.е. число этих независимых наборов Ei.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Graph Coloring»©

Граф G=(V,E).

Найти раскраску G, т.е. разбиение V на непересекающиеся наборы

V1, V2, …, Vk, такие, что каждый Vi независимое множество в G.

Минимизировать размерность раскраски, т.е. число этих независимых наборов Vi.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Clustering»©

  • Конечное множество X, расстояние , для каждой пары, удовлетворяет неравенству треугольника.
  • Найти подразделение X на непересекающиеся подмножества C1, C2, …, Ck.
  • Минимизировать максимальное расстояние между элементами одного подмножества, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Clustering Sum»©

  • Конечное множество X, расстояние , для каждой пары, удовлетворяет неравенству треугольника.
  • Найти подразделение X на непересекающиеся подмножества C1, C2, …, Ck.
  • Минимизировать сумму всех расстояний между элементами одного подмножества, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Maximum Disjoint Connecting Paths»©

  • Граф G=(V,E), пути на ребрах l: E → N, и некоторая пара вершин s,t в V. Найти два непересекающихся по вершинам пути в G, соединающих s и t, т.е. две последовательности вершин u1, u2, …, um и v1, v2, …, vn, такие что
  • Минимизировать максимальную длину этих путей, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum H-Matching»©

  • Граф и фиксированный граф , с по крайней мере тремя вершинами в каком-нибудь связном компоненте.
  • Найти H-сочетание для G, т.е. коллекцию G1, G2, …, Gk, непересекающихся подграфов G, каждый из которых изоморфен H.
  • Максимизировать размерность H-сочетаний, т.е. число непересекающихся подграфов Gi.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Bin Packing»©

  • Конечное множество элементов U, с заданными размерами , и емкость контейнера — положительное целое B.
  • Найти разбиение U на непересекающиеся множества U1, U2, …, Um, такие что сумма размеров элементов в каждом Ui не превышает B.
  • Минимизировать число используемых контейнеров, т.е. число непересекающихся множеств, m.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Clique Cover»©

  • Граф G=(V,E).
  • Найти покрытие кликами для G, т.е. коллекция подмножеств вершин V1, V2, …, Vk, таких, что каждая порождает полный подграф, и каждое ребро (u,v) ∈ E содержит оба своих конца в одном из Vi.
  • Минимизировать размер «k» этого покрытия кликами.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Clique Partition»©

  • Граф G=(V,E).
  • Найти разбиение на клики G, т.е. разбиение вершин V на непересекающиеся подмножества V1, V2, …, Vk, такие что для всех 1≤i≤k, подграф, порожденный вершинами из Vi будет полным графом.
  • Максимизировать размер этого разбиения.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Color Sum»©

  • Граф G=(V,E).
  • Найти раскраску G, т.е. разбиение V на непересекающиеся наборы V1, V2, …, Vk, такие, что каждый Vi независимое множество в G.
  • Минимизировать «сумму раскрасок», т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Longest Path»©

  • Граф G=(V,E).
  • Найти простой путь в G, т.е. набор различных вершин v1, v2, …, vm, такой что .
  • Минимизировать длину пути, т.е. число ребер в этом пути.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Capacitated Tree Partition»©

  • Граф G=(V,E) с весами w: E → N.
  • Найти k-мощное разбиение G на деревья, т.е. непересекающаяся коллекция подмножеств E1, …, Em ребер из E, так, что подграф порожденный каждым Ei будет давать дерево, минимум из k вершин.
  • Минимизировать вес этого разбиения: .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Unsplittable Flow»©

  • Граф G=(V,E), емкости на ребрах , вершина-источник s, коллекция вершин-стоков t1, …, tk, с привязанными неотрицательными целочисленными запросами , такое, что .
  • Найти для каждого типа i единый путь , такой что все запросы удовлетворены, и полный поток проходящий через любое ребро e ограничено c(e).
  • Минимизировать , где f(e) это полный поток проходящий через e.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Independent Sequence»©

  • Граф G=(V,E).
  • Найти независимую последовательность в G, т.е. последовательность независимых вершин, v1, …, vm, таких, что для любого i < m, если вершина соседствует с , но то оно не будет соседствовать ни с одним vj для любого j ≤ i.
  • Максимизировать «m» — длину этой последовательности.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Permutation Group Base»©

  • Группа G перестановок из n символов.
  • Найти базу для G, т.е. последовательность точек b1, …, bk, такой, что единственный элемент в G фиксирующий все эти bi это идентичное преобразование.
  • Минимизировать размер базы, т.е. k.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Schedule Length»©

  • Сеть , где
    • граф G=(V,E)
    • емкость на вершинах b: V → N
    • емкость на ребрах c: E → N
    • T — набор токенов , где , и p — это либо путь из u в v или пустое множество.
  • Найти расписание S, т.е. последовательность f0, …, fl конфигурационных функций , таких что
    • для любого токена , и .
    • для любого и для любого токена t,
      • если и , то
        • (u,v)∈ E
  • Минимизировать длину расписания, l.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Capacity Representatives»©

  • Непересекающиеся множества S1, …, Sm, и для любых , чтобы была задана неотрицательная емкость c(x,y).
  • Найти систему представителей T, т.е. набор T, такой, что для любого i, .
  • Максимизировать «емкость» системы представителей, т.е.

.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Common Point Set»©

  • Положительный целый d, коллекция S1, …, Sk наборов d-мерных точек.
  • Найти множество точек S' конгруэнтное каждому множеству Si из коллекции.
  • Максимизировать размер этого общего набора точек S'.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Common Subtree»©

  • Коллекция T1, …, Tn деревьев.
  • Найти дерево T' изоморфное какому-то поддереву, для каждого Ti.
  • Максимизировать число узлов в этом общем поддереве T'.

Задача в лаб17 (рид-онли просмотр)

Задача «Nearest Lattice Vector»©

  • Базис в решетке , где , точка и положительное целое p.
  • Найти вектор b в решетке, не совпадающий с заданным , но ближайший к нему.
  • Минимизировать расстояние между b0 и b, по норме .

Задача в лаб17 (рид-онли просмотр)

Задача «Shortest Path With Forbidden Pairs»©

  • Граф G=(V,E) и коллекция пар вершин из V, начальная вершина s ∈ V, и конечная вершина f ∈ V.
  • Найти простой путь из s в f, который содержит хотя бы одну вершину из каждой пары в C.
  • Минимизировать длину пути, то есть количество ребер в пути.

Задача в лаб17 (рид-онли просмотр)

Задача «Shortest Weight-Constrained Path»©

  • Граф G=(V,E), длина l: E → N, и вес w: E → N ребер,

выделенные вершины и целое W.

  • Найти простой путь в G весом не больше W, т.е. последовательность различных вершин , таких, что и .
  • Минимизировать длину этого пути, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vehicle Scheduling On Tree»©

  • Дерево с выделенным корнем ,
    • на ребрах заданы времена проезда в
      • прямом f: E → N
      • обратно направлении b: E → N
    • на вершинах
      • время отгрузки-загрузки r: V → N
      • время обработки h: V → N

Найти расписание автомобильного объезда, которое

  • стартует в v0,
  • посещает все вершины в
  • возвращается в v0
  • для любой вершины
    • обработка стартует не раньше .

Т.е. найти перестановку вершин , и функция ожидания w, такую что для любого i где d(u,v) означает длину уникального пути из u в v.


Минимизировать полное время выполнения, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Point-To-Point Connection»©

  • Граф G=(V,E), веса на ребрах w: E → N и множество стартовых и финишных точек.
  • Найти связь точка-точка, т.е. подмножество ребер E' ⊆ E, таких, что для каждой пары старт-финиш, можно проложить путь в E'.
  • Минимизировать вес этой связи, .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Linear Arrangement»©

  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию .
  • Минимизировать сумму длин ребер в этом упорядочивании, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Switching Network»©

  • Полный граф G=(V,E), расстояния удовлетворяющие неравенство треугольника.
  • Разбиение вершин V.
  • Минимизировать максимальное расстояние между вершинами разных множеств с одним индексом, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Complete Bipartite Subgraph Cover»©

Граф G=(V,E).

Найти полное покрытие двудольными подграфами G, т.е. коллекцию

подмножеств вершин V → , такую, что

  • каждое такое подмножество вершин Vi порождает полный двудольный граф.
  • каждое ребро (u,v) ∈ E содержит оба конца в каком-нибудь Vi

Минимизировать «k» — размер этого покрытия.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Bottleneck Path Matching»©

Граф G=(V,E) с четным числом вершин, и весами на ребрах: w: E → N.

Найти непересекающиеся по пути совершенные сочетания для G, т.е. коллекция

непересекающихся простых путей в G с различными финишными вершинами.

Минимизировать вес самого «тяжелого» пути в этих сочетаниях, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Bandwidth»©

  • Граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию .
  • Минимизировать «пропускную способность» этого упорядочивания, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Priority Flow»©

  • Направленный граф G=(V,E), вершины-источники , вершины-стоки , емкость ребер c: E → R, ограничения на вершинах b: V → R, и для любой вершины v, есть некий порядок исходящих ребер.
  • Найти приоритетный поток f, т.е. функция f: E→R, такая что
    • для любого ребра e, f(e) ≤ c(e)
    • для любой вершины , поток сохраняется в v
    • для любой вершины v
      • поток покидающий v не превышает b(v)
      • для исходящей любой пары ребер , если и , то .
  • Максимизировать поток, приходящей в первый сток t1, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Satisfiability Of Quadratic Equations Over Gf(Q)»©

  • Простое число q, набор полиномов степени не большей 2, над полем GF[q] от n переменных. Эти полиномы не должны содержать мономов .
  • Найти в подмножество полиномов P'⊆ P, у которых будет некий общий корень.
  • Максимизировать размер этого подмножества, т.е. P'.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum D-Vector Covering»©

  • Набор X векторов из .
  • Найти разбиение X на m подмножеств
  • Максимизировать покрывающих подмножеств среди , где «покрывающим» подмножество S векторов из , считается, если для всех i ≤ d сумма i-х компонент элементов из S будет не меньше 1.

Задача в лаб17 (рид-онли просмотр)

Задача «Longest Path With Forbidden Pairs»©

  • Граф G=(V,E) и коллекция пар вершин из V.
  • Найти простой путь в G, который содержит хотя бы одну вершину из каждой пары в C.
  • Минимизировать длину пути, то есть количество ребер в пути.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Chordal Graph Completion»©

  • Граф G=(V,E).
  • Найти «хордальный граф», который содержит G, как подграф, т.е. E ⊆ E'.
  • Минимизировать размер хордального графа, |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Interval Graph Completion»©

  • Граф G=(V,E).
  • Найти интервальный граф, который содержит G, как подграф, т.е. E ⊆ E'.
  • Минимизировать размер интервального графа, |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Independent Dominating Set»©

  • Граф G=(V,E).
  • Найти независимый доминирующий набор вершин G, т.е. подмножество V'⊆V, такое, что для всех u ∈ V-V' есть
  • v ∈ V'
  • ребро (u,v)∈ E,
  • и при этом нет двух вершин в V' соединенных ребром из E.

Минимизировать мощность доминирующего набора вершин, |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Job Shop Scheduling»©

  • процессоров (станков, рабочих мест и т.п.), набор работ J, каждая работа j∈J
    • состоит из последовательности из nj операций с , для каждой такой операции
      • требуется процессор
      • и длина .
  • Найти «расписание работы цеха» для J, набор однопроцессорных расписаний, , такое, что
    • из следует
  • Минимизировать время выполнения расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Ratio-Cut»©

  • Граф G=(V,E), пропускная способность на ребрах c: E → N, k

товаров, т.е., k пар , и запросы di для каждой пары.

  • Найти разрез, т.е. разбиение V на два непересекающихся набора V1 и V2.
  • Минимизировать емкость разреза деленную на объем запросов через этот разрез:

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Resource Constrained Scheduling»©

  • Набор задач T с длинами l(t), m процессоров, число ресурсов , ресурсные потребности задач и ресурсные ограничения bi.
  • Найти m-процессорное расписание для T, соблюдающую ресурсные ограничения, т.е. функцию f: T → Z, такую что
    • , если S(u) будет набор задач t для которых , то и
  • Минимизировать общую длительность расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Time-Cost Tradeoff»©

  • Набор активностей J, направленный ациклический граф определяющий отношения предшествования для активностей, , длительности , положительный бюджет B, и для каждой активности j ∈ J задана монотонно невозрастающая ступенчатая функция с lj ступенями:

, где .

  • Найти однопроцессорное расписание для J которое соблюдает отношения предшествования, длительности задач и укладывается в бюджет .

StasFomin 07:13, 12 апреля 2023 (UTC): Что-то на первый взгляд очень странное, штраф за первую задачу всегда будет бесконечным, непонятно.

  • Минимизировать общее время всех активностей

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Diameters Decomposition»©

  • Граф G=(V,E).
  • Декомпозиция графа на два фактора F1 и F2 с одинаковыми диаметрами.
  • Минимизация диаметра F1.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Edge Dominating Set»©

Граф G=(V,E).

Найти доминирующий набор ребер G, т.е. подмножество E' ⊆ E, такое, что для всех

, где , такой что e1 и e2 совместны.

Минимизировать мощность доминирующего набора ребер |E'|

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Height Two Dimensional Packing»©

  • Набор прямоугольников с положительными размерами (ширина , высота yi).
  • Найти упаковку из прямоугольников B в плоский контейнер единичной ширины и бесконечной высоты. Прямоугольники должны быть упакованы без пересечений и вращать их нельзя.
  • Минимизировать высоту упаковку P.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum 3-Dedicated Processor Scheduling»©

  • Набор задач T, набор P из 3 процессоров, каждая задача t ∈ T имеет
    • длительность
    • требуемое подмножество процессоров r(t)⊆P .
  • Найти расписание для T, т.е. функция возвращающая время старта , такую что для любых двух задач t1 и t2, у которых , либо
  • Минимизировать полное время расписания

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Broadcast Time»©

  • Граф G=(V,E), вершина-источник .
  • Найти схему вещания. В момент «0» только v0 содержит сообщение, которое надо передать в кажду вершину. В каждый момент любая вершина, котора получила сообщение, может передать это сообщение максимум одному из своих соседей.
  • Минимизировать время передачи, т.е. момент времени, когда все вершины получат сообщение.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Constrained Partition»©

  • Конечное множество A и размер для каждого его элемента a ∈ A, выделенный элемент , и подмножество S⊆A.
  • Найти разбиение A, т.е. подмножество A' ⊆ A, такой, что
  • число элементов из S на той стороне разбиения, где a0.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Hyperplane Consistency»©

  • Конечные множества P и N целочисленных n-мерных векторов.
    • P — положительные примеры
    • N — отрицательные примеры.
  • Найти гиперплоскость заданную вектором нормали и смещением w0.
  • Максимизировать число примеров, удовлетворяющих этой гиперплоскости:
.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Common Embedded Sub-Tree»©

  • Деревья T1 и T2 с метками на вершинах.
  • Найти общее встроенное поддерево, т.е. помеченное дерево T', которое можно встроить в оба исходных дерева. Встраивание из T' в T, это инъективная функция от вершин T' в вершины T, которая сохраняет метки и отношения предшествования (пропускать предшественников можно).
  • Максимизировать размер общего поддерева, |T'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Geometric 3-Degree Spanning Tree»©

  • Множество P ⊆ Z×Z точек на плоскости.
  • Найти остовное дерево T для P, в котором нет вершин степени большей 3.
  • Минимизировать полный вес этого дерева, , где d(u,v) — евклидово расстояние между u и v.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Geometric Disk Cover»©

  • Множество точек на целочисленной плоскости P ⊆ Z×Z.
  • Найти набор центров C ⊆ Q×Q на Евклидовой плоскости, такой, что каждая точка в P будет покрыта диском с радиусом и центром в одной из точек в C.
  • Минимизировать размер этого дискового покрытия, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Geometric Steiner Tree»©

  • Набор точек на плоскости P ⊆ Z×Z.
  • Найти конечный набор точек Штейнера, Q ⊆ Z×Z.
  • Минимизировать полный вес минимального остовного дерева для набора вершин , где вес ребра это округленная евклидова длина

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Multi Cut»©

  • Граф G=(V,E), набор S ⊆ V×V пар «источник-терминал», веса на ребрах w: E → N.
  • Найти мультиразрез, т.е. набор ребер E' ⊆ E, удаление которых отсоединит каждый терминал от своего источника.
  • Минимизировать вес разреза, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Generalized Steiner Network»©

  • Граф G=(V,E), веса w: E → N и пропускная способность c: E → N на ребрах, функция требований r: V×V → N.
  • Найти сеть Штейнера над G которая удовлетворит требованиям, не превысив пропускные способности, т.е. функция f: E → N, такая, что для каждого ребра e, и для любой пары вершин i и j, число непересекающихся по ребрам путей между i и j будет как минимум r(i,j), при этом, для кадого ребра e можно использовать f(e) копий ребра e.
  • Минимизировать .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Strong Connectivity Augmentation»©

  • Направленный граф G=(V,A), и весовая функция w: V×V → N.
  • Найти набор дуг A' дополнения G до связности, т.е. A' — упорядоченные пары вершин из V, такие что сильно связан.
  • Минимизировать вес дополняющего набора .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Sequencing With Release Times»©

  • Набор задач T, для каждой задачи есть
    • время релиза (раньше запускать задачу нельзя)
    • длина
    • вес
  • Найти однопроцессорное расписание для T, которое соблюдает времена релиза, т.е. функция f: T → N, которая
    • , если S(u) это набор задач t, для которых , то (в процессе только одна задача)
    • (раньше релиза не запускаем)
  • Минимизировать взвешенную сумму времен завершения

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Single Sink Edge Installation»©

  • Граф G=(V,E), пути на ребрах l: E → N, набор вершин-источников S⊆V, сток t ∈ V, функция запросов , конечный набор типов кабелей, характеризующихся емкостью и стоимостью единицы длины.
  • Найти сеть из этих кабелей, т.е. количество кабелей каждого типа для каждого ребра, причем такое, чтобы выполнить все запросы из источников к стоку. Запрос каждого источника должен идти по одному пути от источника к стоку.
  • Минимизировать полную стоимость этой сети.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Steiner Tree»©

  • Полный граф G=(V,E), метрика — веса на ребрах s: E → N, некоторое подмножество S⊆V требуемых вершин.
  • Найти дерево Штейнера, т.е. поддерево G которое включает все вершины из S.
  • Минимизировать сумму весов ребер этого поддерево.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum File Transfer Scheduling»©

  • Граф передачи файла, т.е. граф G=(V,E), ограничения пропускной способности на вершинах, p: V → N и функция длины файлов на ребрах L: E → N.
  • Найти расписание передачи файла, т.е. функция s: E → N, такая что для каждой вершины v и для каждого момента t ∈ N,
  • Минимизировать время выполнения расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Multiway Cut»©

  • Граф G=(V,E), набор S⊆V терминалов, веса на ребрах w: E → N.
  • Многопутевой разрез, т.е. набор ребер E' ⊆ E, удаление которых отсоединит каждый терминал от других.
  • Минимизировать вес разреза, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Network Inhibition On Planar Graphs»©

  • Граф G=(V,E), пропускная способность ребер c: E → N, стоимость разрушения ребра d: E → N, и бюджет B.
  • Найти стратегию атаки на эту сеть, т.е. функцию , такую, что .
  • Минимизировать пропускную способность поврежденной сети, т.е. минимальный разрез в G с емкостью .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Precedence Constrained Scheduling»©

  • Набор задач T, m процессоров, единичная время-длина , частичный подрядок предшествования на T.
  • Найти m-процессорное расписание для T, соблюдающую отношения предшествования, т.е. функцию f: T → N, такую что
    • из t < t' следует f(t') > f.
  • Минимизировать время выполнения расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Quotient Cut»©

  • Граф G=(V,E), веса на вершинах w: V → N, стоимости на ребрах c: E → N.
  • Найти разрез C⊆V.
  • Минимизировать коэффициент разреза, т.е.

, где c(C) означает сумму стоимостей ребер (u,v), таких, что либо u ∈ C и v ∉ C или u ∉ C и v ∈ C и для любого подмножества V'⊆V, w(V') означает сумму весов вершин из V'.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Horn Core»©

  • M — набор булевых значений для n переменных.
  • Найти «Horn core» от M, т.е. подмножество M' ⊆ M, такое, что M' набор булевых значений удовлетворяющих формулу Хорна, [1].
  • Размерность ядра, т.е. |M'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Facility Location»©

  • Полный граф G=(V,E), стоимости перемещения , с неравенством треугольника, F⊆V — места, где можно построить место обслуживания (туалеты, магазины, заправки), — стоимость этого строительства, — потребности в разных местах.
  • Найти места для строительства мест обслуживания, F' ⊆ F.
  • Минимизировать

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Hitting Set»©

  • Коллекция C подмножеств конечного множества S.
  • Найти множество представителей (hitting set) для C, т.е. подмножество S' ⊆ S, такое, что S' содержит по крайней мере один элемент из каждого подмножества из C.
  • Минимизировать размер множества представителей, .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Open-Shop Scheduling»©

  • процессоров, множество работ, каждый j ∈ J состоит
    • m операций ( должна выполняться на процессоре i)
    • для каждой такой операции есть длительность .
  • Найти «расписание работы цеха» для J, т.е. коллекцию однопроцессных расписаний ,
    • таких, что из следует , т.е. для каждого j ∈ J, интервалы не пересекаются.
  • Минимизировать время выполнения расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Planar Record Packing»©

  • Коллекция C из n записей,
    • для каждой записи c ∈ C задана некоторая вероятность p(c), .
  • Найти для каждой записи из c ∈ C размещение z(c) на плоскости, заданное целочисленными координатами, так, что все записи расположены на разных точках этой плоскости.
  • Минимизировать 
,

где — дискретное евклидово расстояние между точками и .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Traveling Repairman»©

  • Граф G=(V,E), стартовая вершина r ∈ V, длины на ребрах , удовлетворяющие неравенству треугольника.
  • Найти обход, стартующий в r, обходящий все вершины в G, т.е. перестановка , такая что .
  • Минимизировать , где — полное расстояние пройденное в этом пути от стартовой вершины, до вершины v.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Tree Width»©

  • Граф G=(V,E).
  • Декомпозиция на деревья, т.е. пара , где — некое дерево, и коллекция подмножеств вершин V, такая, что
    • для любого существует
    • для любого v ∈ V множество образует связное поддерево T.
  • Минимизировать ширину дерева в декомпозиции на деревья, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Weighted Satisfiability With Bound»©

  • Набор булевых переменных U, булевое выражение F над U, неотрицательное число-ограничение B ∈ N,
    • для каждой переменной u ∈ U, задан вес , такой что .
  • Найти значения переменных для U, т.е. выбор подмножества U'⊆ U переменных которых выставили в «истину», а остальные U-U' соответственно выставлены в «ложь». Значение решения R будет
    • либо B, если F ложно
    • либо , если F истинно.
  • Максимизировать R.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Dynamic Storage Allocation»©

  • Нужно хранить некий набор A каких-то штук, каждая a ∈ A из которых имеет
    • размер
    • время прибытия
    • время отбытия
  • Найти допустимый план резервирования места хранения, т.е. функция , такая что для любых a,a'∈ A, если непусто, то либо , либо .
  • Минимизировать максимальный требуемый размер, т.е.
.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Flow-Shop Scheduling»©

  • процессоров, множество работ, каждый j ∈ J состоит
    • m операций ( должна выполняться на процессоре i)
    • для каждой такой операции есть длительность .
  • Найти «расписание работы цеха» для J (см. Hardprob/Minimum_Open-Shop_Scheduling), такая что, для каждого j ∈ J, и , .
  • Минимизировать время выполнения расписания, т.е.


Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Graph Motion Planning»©

  • Граф G=(V,E),
    • стартовая вершина s ∈ V, где изначально размещается робот,
    • целевая вершина t ∈ V
    • подмножество вершин W⊆V где изначально находятся препятствия.
  • Найти схему движения робота и этих препятствий. На каждом шагу, либо робот, либо одно препятствие можно переместить на незанятую вершину. Надо переместить робота в целевую вершину.
  • Минимизировать число шагов.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Supplier»©

  • Полный граф G=(V,E), расстояния , удовлетворяющие неравенству треугольника, для вершин v ∈ V заданы стоимость строительство центра , некий «вес» использования , ограничение на бюджет L ∈ N.
  • Места размещения поставок в рамках бюджета, т.е. подмножество вершин S⊆V, для которых .
  • Минимизировать максимальную взвешенную дистанцию от вершины до ближайшего поставщика, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Metric Bottleneck Wandering Salesperson Problem»©

  • Набор C из m городов, стартовый город s ∈ C, финишный город f ∈ C, расстояния удовлетворяющие неравенству треугольника.
  • Найти простой путь из начального города s в финишный город f проходящий через все города из C, т.е. перестановка , такая что и .
  • Минимизировать максимальную длину ребра в пути.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Metric Traveling K-Salesperson Problem»©

  • Набор C из m городов, стартовый город s ∈ C, расстояния удовлетворяющие неравенству треугольника.
  • Найти коллекцию из k подтуров, каждый из которых соедержит начальный город, и каждый город есть хотя бы в одном подтуре.
  • Минимизировать максимальную длину среди этих k подтуров.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Edge Deletion To Obtain Subgraph With Property P»©

  • Направленный или ненаправленный граф G=(V,E) и некое свойство (предикат) P над подграфами.
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G=(V, E-E') имеет свойство P.
  • Минимизировать размер этого удаляемого множества ребер |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Edge Deletion K-Partition»©

  • Граф G=(V,E), с весом на ребрах w: E → N.
  • Найти «k»-разбиение вершин («раскраску») c: V → [1..k]
  • Минимизировать вес одноцветных ребер, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Constrained Sequencing To Minimize Tardy Task Weight»©

  • Набор T задач, для каждой задачи t ∈ T есть длина , вес и дедлайн , подмножество S ⊆ T и положительное целое K.
  • Найти однопроцессорное расписание σ для T, такая что сумма w(t) по всем t ∈ T для которых не превосходит K.
  • Максимизировать число работ в S, выполненных в срок.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Dominating Set»©

  • Граф G=(V,E).
  • Найти «доминирующий набор» для G, то есть подмножество V'⊆V такое что для всех u ∈ V-V' cуществует v ∈ V' для которого (u,v) ∈ E.
  • Оптимизировать «кардинальность доминирующего набора», то есть, |V'| → min.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Directed Bandwidth»©

  • Направленный ациклический граф G=(V,E).
  • Найти линейное упорядочивание V, т.е. биективную функцию f: V→ {1,2,…,|V|}, такую что (u,v)∈ E, f(u)<f(v).
  • Минимизировать «пропускную способность» этого упорядочивания, т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Diameter Spanning Subgraph»©

  • Граф G=(V,E), на ребрах e ∈ E заданы вес и длина l(e)∈ N, положительное число B.
  • Найти остовный подграф E' ⊆ E для G, такой, что сумма весов ребер в E' не превосходит B.
  • Минимизировать диаметр остовного подграфа.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Stacker Crane Problem»©

  • Смешанный (ориентированные дуги и неориентированные ребра) граф , длины на ребрах l(e)∈ N для каждого ребра и дуги .
  • Найти коллекцию из k циклов, каждый содержит начальную вершину s, такая, что их совокупность включает каждое дугу графа.
  • Минимизировать максимальную длину среди этих k циклов.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Stacker Crane Problem»©

  • Смешанный (ориентированные дуги и неориентированные ребра) граф , длины на ребрах l(e)∈ N для каждого ребра и дуги , такой, что для каждой дуги, есть параллельное ребро где длина не больше.
  • Найти цикл в G (возможно с повтором вершин), такой что включает каждое направленную дугу в A по крайней мере один раз, проходя по ним в правильном направлении.
  • Минимизировать тотальную длину цикла.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vertex Cover»©

Граф .

Найти, «вершинное покрытие» для «G», т.е.подмножество V'⊆V, такое, что

для каждого ребра (u,v)∈ E, по меньшей мере одна вершина — «u» или «v» принадлежит V'.

Оптимизируем размерность вершинного покрытия, т.е. |V'|

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Crossing Number»©

  • Направленный граф G=(V,A).
  • Найти размещение графа на плоскости.
  • Минимизируя число пересекающихся пар ребер.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Feedback Arc Set»©

Направленный граф G=(V,A).

Найти множество ребер разрезающее циклы,

т.е. подмножество , такое, что A' содержит по крайней мере одну дугу из каждого направленного цикла в G.

Минимизировать размерность этого подмножества, .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Feedback Vertex Set»©

Направленный граф G=(V,A).

Найти множество вершин разрезающее циклы,

т.е. подмножество , такое, что V' содержит по крайней мере одну вершину из каждого направленного цикла в G.

Минимизировать размерность этого подмножества, |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Communication Cost Spanning Tree»©

  • Полный граф G=(V,E), веса на ребрах w(e)∈N, e∈E, некоторое требование для каждой пары вершин r({u,v})∈N.
  • Найти основное дерево для G.
  • Минимизировать взвешенную сумму по всем парам вершин стоимостей путей по парам вершин в T, т.е., , где W(u,v) означает сумму весов ребере на пути, соединающем u и v в T.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Precedence Constrained Sequencing With Delays»©

  • Набор задач T, положительное целое D, для каждой задачи есть целочисленная задержка ,
    • направленный ациклический граф , определяющий отношения предшествования для этих задач.
  • Найти одно-процессорное расписание для T, соблюдающее отношения предшествования и задержки, т.е. инъективная функция , такая, что для каждого ребра , выполняется
  • Минимизировать время выполнение всего расписания.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Local Register Allocation»©

  • Набор инструкций, формирующих некий блое без переходов,
    • N доступных регистров,
    • стоимость чтения и записи в регистр i.
  • Порядок резервирования регистров для этой последовательности инструкций.
  • Минимизировать полную стоимость чтения-записи в регистры.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Generalized 0-1 Assignment»©

  • Целая m×n-матрица , целый m-вектор и целая m×n-матрица .
  • Найти m×n-матрицу , в которой только одна единица в каждой колонке, и

.

  • Минимизировать 
.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Block-Angular Convex Programming»©

  • K непересекающихся выпуклых компактных множеств, блоков
  • M неотрицательных непрерывных выпуклых функций .
  • Найти положительное число λ, такое что

  • Минимизировать λ.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Array Partition»©

  • Массив n×n неотрицательных целых A, положительное число p.
  • Найти
    • p-1 горизонтальных делителей
    • p-1 вертикальных делителей
    • разбивающих A на блоков.
  • Минимизировать максимальный «вес» блока

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Length Triangulation»©

  • Коллекция пар целых, задающих координаты на плоскости.
  • Найти триангуляцию набора точек из C, т.е. коллекция E непересекающихся отрезков соединающих некоторые точки из C, так, что внутренность этой выпуклой оболочки подразделена на треугольники.
  • Минимизировать округленно-евклидову длину триангуляции, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Spanning Tree»©

  • Граф G=(V,E), целое , веса на ребрах w: E → N.
  • Найти k-остовное дерево, т.е. дерево T, подграф G с по крайней мере k вершинами.
  • Минимизировать вес этогго дерева .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Chinese Postman For Mixed Graphs»©

  • Мультиграф, начальная вершина s∈V, длина l(e)∈N для каждого ребра e ∈ E.
  • Найти коллекцию из k циклов, каждый содержит начальную вершину s, такая, что их совокупность включает каждое ребро графа.
  • Минимизировать максимальную длину среди этих k циклов.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Two-Processor Flow Shop Scheduling With Batch Set-Up Times»©

такой, что для если две операции и , с распланированы последовательно (т.е. нет другой операции , для которой ), и требуют разных компиляторов (т.е. ), то .

  • Минимизировать время выполнения расписания, т.е.
.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Unsatisfying Linear Subsystem»©

  • Система линейных уравнений Ax=b, где A целочисленная m×n—матрица, и целочисленный m-вектор b.
  • Найти рациональный n-вектор .
  • Минимизировать число уравнений, которые не выполняются найденным x.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Tree Compact Packing»©

  • Дерево T=(V,E),
    • нормализованный вес на вершинах , ,
    • некоторая страничная емкость p.
  • Найти компактную упаковку T на страницах емкости p, т.е. функция , такая, что
  • Минимизировать страничные сбои этой упаковки, т.е.

, где

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Test Collection»©

  • Коллекция C подмножеств конечного множества S.
  • Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов , есть некоторое множество , которое содержит точно один элемент из этой пары.
  • Минимизировать мощность этой подколлекции |C'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Storage Time Sequencing»©

  • Набор задач T, для каждой задачи есть длина ,
    • направленный ациклический граф , определяющий отношения предшествования для этих задач, для каждого ребра этого графа есть вес , измеряющий некий объем хранения, нужный для передачи промежуточных результатов между этими задачами.
  • Найти одно-процессорное расписание для T, соблюдающее отношения предшествования, т.е. перестановка , такая что для каждого ребра выполняется .
  • Минимизировать произведение затрат на хранение и времени, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Routing Tree Congestion»©

  • Граф G=(V,E), веса w: E → N на ребрах.
  • Найти маршрутное дерево T для G, т.е. дерево T, для которого все внутренние вершины имеют степень 3, а листья соответствуют вершинам G.
  • Минимизировать перегруженность дерева маршрутизации, т.е. минимум по максимуму для каждого ребра e по , и где

S — это один из двух связных компонентов, полученных удалением e из T.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Relevant Variables In Linear System»©

  • Целочисленная m×n матрица , целый m-вектор .
  • Рациональный n-вектор , такой что Ax=b.
  • Минимизировать число ненулевых элементов в x.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Quadratic 0-1 Assignment»©

  • Неотрицательная целая n×n-матрица , неотрицательная целая m×m-матрица .
  • Найти бинарную матрицу -матрицу , такую, что в каждой строке не большое одной единицы, и точно одна единица в каждой колонке.
  • Минимизировать 
.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Multiprocessor Scheduling With Speed Factors»©

  • Набор задач T, m процессоров…
    • для каждой задачи t ∈ T есть длительность
    • для каждого процессора есть фактор скорости , где s(1)=1 и .
  • Найти m-процессорное расписание для T, т.е. функцию .
  • Минимизировать время завершения расписания, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Metric Dimension»©

  • Граф G=(V,E).
  • Найти метрический базис для G, т.е. подмножество V'⊆V, такое, что для каждой пары есть , что длина кратчайшего пути из u в w отличается от длины кратчайшего пути из v в w.
  • Минимизировать размер этого метрического базиса, |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Median»©

  • Полный граф G=(V,E) и расстояния .
  • Найти k-медианное множество, т.е. подмножество .
  • Минимизировать расстояния от каждой вершины до ближайшей медианы, т.е.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum K-Center»©

  • Полный граф G=(V,E) и расстояния , удовлетворяющие неравенству треугольника.
  • Найти к-центр, т.е. подмножество , с минимальным расстоянием от всех вершин до какого-то узла из этого множества.
  • Минимизировать максимальное расстояние от каждой вершины до ближайшего к ней «центра»:

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Graph Inference»©

  • Класс C ненаправленных графов с раскраской ребер из строки цветов x.
  • Найти граф и простой путь в нем, такой, что строка-последовательность ребер на этом пути как раз будет равна x.
  • Минимизировать размер множества ребер в G.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Equivalent Digraph»©

  • Направленный граф G=(V,E).
  • Найти подмножество E' ⊆ E, такое что для каждой пары вершин , граф G'=(V,E') содержит направленный путь из u в v, тогда и только тогда, когда этот путь есть в оригинальном графе G.
  • Минимизировать размер E', т.е. |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Biconnectivity Augmentation»©

  • Граф G=(V,E), и симметричная весовая функция w: V×V → N.
  • Найти набор ребер E' дополнения G до связности, т.е. E' — неупорядоченные пары вершин из V, такие что G'=(V, E ∪ E') двусвязен.
  • Минимизировать вес дополняющего набора .

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Satisfying Linear Subsystem»©

  • Система линейных уравнений Ax=b, где A целочисленная m×n—матрица, и целочисленный m-вектор b.
  • Найти рациональный n-вектор .
  • Максимизировать число уравнений, которые выполняются найденным x.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Renamable Horn Subformula»©

  • Набор булевых переменных U, коллекция C скобок-конъюнкций не больше чем из трех литералов.
  • Найти переименовываемую хорнову подформулу C' от C, т.е. подмножество C'⊆ C, т.к. здесь существует подмножество S ⊆ U, таких переменных, что перестановка литералов в делает C' хорновой булевой формулы, где .
  • Максимизировать размер подформулы, т.е. |C'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum K-Facility Dispersion»©

  • Полный граф G=(V,E), расстояния , с неравенством треугольника.
  • Найти набор для размещения k мест обслуживания (туалеты, магазины, заправки), подмножество .
  • Минимизировать минимальное расстояние между двумя такими местами:

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum K-Facility Location»©

  • Полный граф G=(V,E), доходы .
  • Найти места для строительства мест обслуживания, .
  • Максимизировать максимальный полный доход

.

Задача в лаб17 (рид-онли просмотр)

Задача «Longest Common Subsequence»©

  • Конечный алфавит Σ, конечный набор R строк из .
  • Найти строку , такую она является подпоследовательностью любой строки x ∈ R, т.е. ее можно получить вычеркивая символы из любого x.
  • Максимизировать длину этой подпоследовательности .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Bounded Diameter Augmentation»©

  • Граф G=(V,E), положительное целое .
  • Найти дополняющий набор новых ребер E' для G, т.е. набор E' неупорядоченных пар вершин из V, такой что G'=(V, E ∪ E') имеет диаметр D, т.е. максимальное расстояние между любыми парами вершин будет не больше чем D.
  • Минимизировать размер дополняющего множества |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Rectangle Tiling»©

  • Массив n×n неотрицательных целых A, положительное число p.
  • Найти разбиение A на непересекающихся квадратных подмассивов.
  • Минимизировать максимальный «вес» (сумма элементов) подмассива из разбиения.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Quadratic Assignment»©

  • Неотрицательные симметричные n×n матрицы A и B.
  • Найти перестановку .
  • Максимизировать .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Rectilinear Global Routing»©

  • -массив шлюзов, коллекция сетей C, т.е. наборов по три шлюза.
  • Найти прямые отрезки-связи соединяющие шлюзи в каждой сети.
  • Минимизировать самое большое число связей, соединающих два шлюза в данном массиве.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Not-All-Equal 3-Satisfiability»©

  • Множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше 3.
  • Найти истинное присваивание для U, и подмножество скобок C'⊆ C, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.
  • Максимизировать размер этого подмножества |C'| → max

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Minimum Spanning Tree Deleting K Edges»©

  • Граф G=(V,E), веса w: E → N на ребрах.
  • Найти подграф E' ⊆ E из k ребер, и минимальное остовное дерево T в графе (V,E-E').
  • Минимизировать вес T.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Minimum Metric K-Spanning Tree»©

  • Граф G=(V,E), длина ребер l(e) ∈ N ∀e∈E удовлетворяют неравенству треугольника.
  • Найти подмножество V'⊆V, такое, что |V'|=k
  • Максимизировать стоимость минимального остовного дерева подграфа, порожденного V'.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Maximal Matching»©

Граф G=(V,E).

Найти максимальное паросочетание E', т.е. подмножество E' ⊆ E, такое, что

никакие два ребра не содержат одну вершину, но каждое ребро из E-E' с кем-то содержит общую вершину с каким-либо ребром из E' (т.е. добавить «еще одну пару» нельзя).

Минимизировать размерность паросочетания |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum K-Colorable Subgraph»©

  • Граф G=(V,E).
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G'=(V,E') может быть раскрашен в k-цветов, т.е. есть раскраска G' размерности не больше k.
  • Максимизировать мощность этого подграфа |E'|

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Subforest»©

  • Дерево G=(V,E) и набор деревьев H.
  • Найти подмножество ребер E' ⊆ E, такое, что подграф G'=(V,E') не содержит ни одного поддерева изоморфного какому-нибудь дереву из H.
  • Максимизировать мощность этого подграфа |E'|

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Planar Subgraph»©

  • Граф G=(V,E).
  • Найти подмножество ребер E' ⊆ E, такое что подграф G'=(V,E') — планарный.

Максимизировать размер этого планарного подграфа, |E'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Induced Connected Subgraph With Property P»©

  • Граф G=(V,E) и некое свойство (предикат) P над подграфами.
  • Найти подмножество вершин V'⊆V, такое, что подграф порожденный вершинами V' — связный и имеет свойство P.
  • Максимизировать размер этого множества |V'| → max.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Independent Set»©

  • Граф G=(V,E).
  • Найти независимое множество вершин, т.е. подмножество V'⊆V, такое что нет пары вершин в V', соединенных ребром из E.
  • Максимизировать размер этого независимого множества |V'| → max

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Clique»©

  • Граф G=(V,E).
  • Найти клику в G, т.е. подмножество вершин V'⊆V, такое что любая пара вершин в V' соединены ребром из E.
  • Максимизировать размер клики, т.е. |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vertex Deletion To Obtain Connected Subgraph With Property P»©

Направленный или ненаправленныый граф G=(V,E) и некое свойство (предикат) P над подграфами.

Найти подмножество вершин V'⊆V, такое, что подграф порожденный вершинами V-V' — связный и

имеет свойство P.

Минимизировать размер этого множества |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vertex Deletion To Obtain Subgraph With Property P»©

Направленный или ненаправленный граф G=(V,E) и некое свойство (предикат) P над подграфами.


Найти подмножество вершин V'⊆V, такое, что подграф порожденный V-V' имеет свойство P.


Минимизировать размер этого удаляемого множества вершин |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum K-Colorable Induced Subgraph»©

  • Граф G=(V,E).
  • Найти подмножество V'⊆V, такое, что порожденный подграф k-раскрашиваем, т.е. есть раскраска G', размерности не больше чем k.
  • Минимизировать размер этого подмножества, |V'|.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Vertex Disjoint Cycle Cover»©

Граф G=(V,E).

Найти семейство F непересекающихся по вершинам циклов, покрывающих V.

Минимизировать число этих циклов в F.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Bend Number»©

  • Направленный планарный граф G=(V,E)
  • Найти планарный ортогональный чертеж графа G, т.е. отрисовка вершин G как точек плоскости, а ребер как последовательностей горизонтальных и вертикальных отрезков, так, что нет пересечений.
  • Минимизировать число сгибов на чертеже.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Leaf Spanning Tree»©

  • Граф G=(V,E).
  • Найти остовное дерево G.
  • Минимизировать число листьев в этом остовном дереве.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Edge K-Spanner»©

  • Связный граф G=(V,E) с весами на ребрах w: E → N, положительное целое k.
  • Найти k-остов G, т.е. G' — остовной подграф G такой, что для любой пары вершин u и v, длина кратчайшего пути между u и v в G' будет не больше чем в k раз больше, чем кратчайший путь между u и v в исходном графе G.
  • Минимизировать число ребер в G' (вариант — минимизировать сумму весов ребер G').

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Degree Spanning Tree»©

  • Граф G=(V,E).
  • Найти остовное дерево T для G.
  • Минимизировать максимальную степень этого дерева.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Locally Testable Automaton Order»©

  • Локально тестируемый язык L, т.е. некий язык L, такой, что положительное целое j, такое что входит или нет строка x в этот язык зависит от …
    • префикса и суффикса x длины j-1,
    • набора подстрок x длины j.
  • Найти порядок j, т.е. положительное целое j, «свидетель» локальной тестируемости L.
  • Минимизировать значение порядка, т.е. j.

Задача в лаб17 (рид-онли просмотр)

Задача «Shortest Computation»©

  • Недетерминированная машина Тьюринга M, двоичная входная строка x.
  • Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
  • Минимизировать длину кратчайшей из этих строк,т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Longest Computation»©

  • Недетерминированная машина Тьюринга M, двоичная входная строка x.
  • Найти недерминированную строку-догадку c, произведенную машиной M на входе x.
  • Максимизировать длину кратчайшей из этих строк,т.е. .

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Consistent Finite Automaton»©

  • Два конечных множества P, N двоичных строк.
  • Найти детерминированный конечный автомат , который принимает все строки из P и отвергает все строки из N.
  • Минимизировать число состояний в автомате.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Length Equivalent Frege Proof»©

  • Доказательство Фреге π для некоторой тавтогологии φ.
  • Найти более короткое доказательство Фреге π' для φ, более короткое чем π, т.е. содержащая не больше символов чем π.
  • Минимизировать число символов в π'.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum K-Constraint Satisfaction»©

  • Набор булевых переменных U, коллекция C конъюнкций, не больше k литералов (литерал — переменная или ее отрицание),
  • Найти присваивание переменным из U.
  • Максимизировать число выполненных скобок-дизъюнкций.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Equivalence Deletion»©

  • Набор булевых переменных U, коллекция C равенств, т.е. пар литералов над переменными из U.
  • Найти присваивание переменным U.
  • Минимизировать число невыполненных равенств.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Number Of Satisfiable Formulas»©

  • Набор булевых переменных U, коллекция C 3CNF-формул.
  • Найти присваивание переменным U.
  • Минимизировать число выполненных формул.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Number Of Satisfiable Formulas»©

  • Набор булевых переменных U, коллекция C 3CNF-формул.
  • Найти присваивание переменным U.
  • Максимизировать число выполненных формул.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Distinguished Ones»©

  • Непересекающиеся множества булевых переменных X,Z, коллекция C дизъюнкций не больше чем три литерала, где каждый литерал переменная или отрицание из X∪Z.
  • Найти присваивание для X и Z, чтобы все скобки в C выполнялись.
  • Минимизировать число переменных из Z, которые будут установлены в «истину».

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Distinguished Ones»©

  • Непересекающиеся множества булевых переменных X,Z, коллекция C дизъюнкций не больше чем три литерала, где каждый литерал переменная или отрицание из X∪Z.
  • Найти присваивание для X и Z, чтобы все скобки в C выполнялись.
  • Максимизировать число переменных из Z, которые будут установлены в «истину».

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum 3-Dnf Satisfiability»©

  • Множество переменных U,
  • Коллекция C скобок-конъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше 3.
  • Найти присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

Задача «Maximum Satisfiability»©

  • Множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание.
  • Найти истинное присваивание для U.
  • Максимизировать число скобок.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Travel Robot Localization»©

  • Простой многоугольник P и многоугольник видимости V внутри P, где робота станет видно.
  • Найти схему движения робота до момента, когда его станет видно.
  • Минимизировать расстояние пройденного роботом.

Задача в лаб17 (рид-онли просмотр)

Задача «Minimum Rectangle Cover»©

  • Произвольный многоугольник P.
  • Найти коллекцию из m прямоугольников, чье объединение точно эквивалентно многоугольнику P.
  • Минимизировать m — число элементов в этой коллекции.

Задача в лаб17 (рид-онли просмотр)

Задача «[[Зарезервированные практические задачи|]]»©

Всего страниц найдено: 12.

----

Бонусная задача

Докажите, что для каждого целого числа n существует раскраска ребер полного графа K_n в два цвета, такое что полное число одноцветных подграфов K_4 будете не больше чем \binom{n}{4} 2^{-5}

Задача зарезервирована: StasFomin 11:32, 19 мая 2023 (UTC)

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=Теоретические_задачи notcategory=Solved notcategory=Решенные_задачи ignore=Permission denied ignore=A ignore=Open_Exercises ignore=Открытые_теоретические_задачи


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Минимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Abel1502 09:57, 25 мая 2023 (UTC)


  • Константа k≥2, множество переменных U,
  • Коллекция C скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше k.
  • Найти истинное присваивание для U.
  • Максимизировать число выполненных скобок.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП.
  • Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.

Задача зарезервирована: Abel1502 08:50, 11 мая 2023 (UTC)


  • Набор задач T, m процессоров, время выполнения l(t,i)∈ Z^+, \ \ ∀t∈ T, \ i∈ [1..m].
  • Найти m-процессорное расписание для T, т.е. функцию f: T→ [1..m].
  • Минимизировать время выполнения расписания, т.е. 
\max\limits_{i∈ [1..m]}\displaystyle\sum\limits_{t∈  T: \atop f(t)=i} l(t,i) → min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: JulesIMF 15:31, 28 мая 2023 (UTC)


  • Три множества X, Y, W и функция стоимости c: X×Y×W → N
  • Найти назначение A, т.е. подмножество A ⊆ X×Y×W, такой что каждый элемент из X ∪ Y ∪ W принадлежит только одной тройке из A.
  • Минимизировать стоимость назначения, т.е.

\sum_{(x,y,w) ∈ A}c(x,y,w) → \min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Krym4s 15:55, 9 мая 2023 (UTC)

Minimum-exact-cover.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти покрытие множества S, на т.е. подмножество C'⊆ C, такое, что для каждый элемент из S принадлежит по крайней мере одному подмножеству из C'.
  • Минимизировать суммарных объем покрывающих подмножеств, т.е. \sum\limits_{c\in C'} |c| → \min

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Анна Савчук 12:55, 25 апреля 2023 (UTC)

Maximum-set-splitting.svg
  • Коллекция C подмножеств конечного множества S.
  • Найти разбиение S, на непересекающиеся множества S1 и S2.
  • Максимизировать число подмножеств C, которые «разделены» между S1 и S2, т.е. не лежат полностью в S1 или S2.

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: Ilya 16:25, 2 мая 2023 (UTC)


  • Набор C из m городов с заданными расстояниями между ними d(c_i,c_j)∈ N для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
  • Найти тур C, т.е. перестановка \pi: [1..m]→ [1..m].
  • Минимизировать длину этого тура

d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1} d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)

Задача в лаб17 (рид-онли просмотр)

Задача зарезервирована: StasFomin 21:17, 26 апреля 2023 (UTC)

Maximum-cut.png
  • Граф G=(V,E).
  • Найти разбиение V на непересекающиеся множества V1 и V2.
  • Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V1, а другой конец в V2.

Задача в лаб17 (рид-онли просмотр)

  • Data-vis-logo.png — есть тестовые данные и визуализация.
  • PyomoLogo.png — есть Pyomo-формулировка для ЦЛП. 📹 видео 📹

Задача зарезервирована: Artklyachin 14:06, 18 мая 2023 (UTC)

showtotal=yes namespace=Main limit=500 order=lastedit desc,pagename output=template template=IncludeCard2 redirect=no category=ClassicHardProblems notcategory=Solved ignore=Permission denied ignore=A ignore=Open Classic Hard Problems


Долгосрочный план выработки электроэнергии учитывает график работы существующих энергоблоков и график установки новых электростанций для удовлетворения спроса на электроэнергию в течение ряда будущих (5) лет при минимально возможных затратах.

Период планирования; 5 лет

Потребность в электроэнергии описывается кривой продолжительности нагрузки (LDC), как показано на рис (цифры на картинке приблизительны, точные будут дальше текстом), по оси ординат — мегаватты, по оси абсцисс — часы.

Планируем генерацию электричества 2022-10-21 16-20-36 image0.png

Площадь под графиком соответствует потребностям производства электроэнергии в мегаватт-часах.

Чтобы модель была простой, например линейной, график аппроксимируется кусочно-постоянной функцией, показанной в виде гистограммы (ступенчатой функции), с

  • «Bars=4».
  • TD — отсечки по горизонтали 
 2920 3650 1280 910

Первый столбец обозначает минимальную нагрузку, столбец «4» — пиковую нагрузку, а два промежуточных — представляют потребность в средней нагрузке.

В любой компании или стране для производства электроэнергии используется несколько различных типов (n=5) технологий, таких как

  • паровые турбины
  • газовые турбины
  • гидроэлектростанции
  • дизель-генераторы
  • комбинированные генераторы

Эти энергоблоки требуют различных затрат, затрат на установку и переменных затрат, и переменная по времени генерации (что-то ломается, что-то амортизируется, что-то улучшается).

CE_{it}, 1 \leq i \leq n; — планируемые мощности существующих генерирующих типов по времени.
    15000 18000  20000  21000  21000
    40000 350000 300000 280000 280000 
    50000 400000 400000 400000 300000
    10000 100000 120000 130000 150000
     1000  11000 12000  14000  16000
VC_{it}; Переменная (на мегаватт) годовая стоимость старой установки типа «i»
    4 4 4 4 4
    5 5 5 5 5
    3 3 3 3 3
    3 3 3 3 3
    1 1 1 1 1

Кроме того, в будущем могут быть добавлены дополнительные мощности.

Например, предположим, что модель решила установить новую установку типа «j=1» мощностью 50 МВт в период «1», она будет существовать в системе до истечения технического срока службы этой установки (Это потому, что продолжительность горизонта планирования, рассматриваемого в этой задаче, короче, чем технический срок службы любого нового энергоблока, доступного на рынке).

FC_{jt}; Фиксированная годовая стоимость новой установки типа «j»
    100 110 110 120 120
    200 200 200 200 200 
    300 290 290 285 285
    200 190 190 180 180
    50 50 50 50 50  ~
FC_{jt}; Фиксированная годовая стоимость новой установки типа «j»


!AF; 80 80 85 85 85 

    85 85 85 85 85
    90 90 90 90 90
    90 90 95 95 95
    85 85 90 90 90~

!PD; 6000 6000 6000 6000 6000 

    9000 10000 110000 12000 13000
    25000 27000 27000 27000 27000
    50000 58000 58000 58000 57000~

!W; 20 50 10 10 10~







Кроме того, они имеют разный технический срок службы и придерживаются разных правил технического обслуживания.

Задача планирования состоит в том, чтобы определить

  • график работы существующих установок,
  • установок нового поколения, которые будут запущены в будущем,
  • и график введения новых установок путем минимизации суммы затрат на установку и эксплуатацию за заданное количество

лет, соблюдая при этом технические и финансовые ограничения.

Как только будет добавлен новый энергоблок с заданной мощностью, этот энергоблок будет эксплуатироваться на протяжении всего горизонта планирования.


С другой стороны, администрация имеет предпочтение между различными типами технологий, то есть между различными генерирующими установками в случае новых установок.

Это предпочтение описывается процентным коэффициентом от минимума, который должен иметь каждый новый блок, по сравнению с общей энергией, установленной в новых блоках.


Пока не додумано, надо доработать

Задача зарезервирована: StasFomin 16:33, 27 ноября 2022 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

Источник — «https://discopal.ispras.ru/index.php?title=Open_Classic_Hard_Problems&oldid=25388»