Мин. Макс. Соответствующая задача

Question

У меня проблема с сопоставлением, и я не знаю, как ее решить:

Given a complete bipartite graph (A, B).
Each node a_i in A, has two states: s(a_i)=0 or s(a_i)=1
Weighted edges are declared as: w(a_i, b_j, s(a_i))

При исправлении конфигурации для состояний проблема становится максимально совпадающей.

Цель состоит в том, чтобы найти конфигурацию с минимальным максимальным соответствием.

Пример:

|A|=|B|=1
w(a_0, b_0, 0) = 5;
w(a_0, b_0, 1) = 9;

Максимальное совпадение - 5 и 9, поэтому 5 - это ответ.(поэтому конфигурация s (a_0) = 0)

Answer 1

Я сомневаюсь, что это домашнее задание, так как спрашивающий использует свое настоящее имя.

К сожалению, обнаружение присвоения состояний с коэффициентом аппроксимации лучше, чем 2 (при условии, что уникальные игры; 1.3606 в противном случае) составляет NP-трудной .Пусть G будет экземпляром минимального покрытия вершин.Множество A имеет вершину для каждого ребра в G. Множество B имеет вершину для каждой вершины в G. Пусть w (a _j , b _k , 0) будет 1, еслименьшая конечная точка ребра, соответствующего a _j , соответствует b _k , а 0 в противном случае.Определите w (a _j , b _k , 1) аналогично в отношении большей конечной точки.Минимальное максимальное совпадение этого экземпляра имеет количество элементов, равное минимальному покрытию вершин G, и последнюю задачу трудно аппроксимировать.

На фронте алгоритмов мы можем заменить внутреннюю задачу сопоставления максимального веса наего линейное программирование двойное, чтобы минимизировать минимум.Здесь y _j - двойственная переменная, соответствующая _j , а z _k - двойственная переменная, соответствующая b _k .

мин ∑ _j y _j + ∑ _k z _k

st

∀j, k.y _j + z _k ≥ (1 - s (a _j )) w (a _j , b _k , 0) + s (a _j ) w (a _j , b _k , 1)

∀j.s (a _j ) ∈ {0, 1}

∀j.y _j ≥ 0

∀k.z _k ≥ 0

Эта формулировка представляет собой программу со смешанными целыми числами, которая может быть атакована без особых усилий человека с помощью готового программного обеспечения (например, GNU Linear).Комплект для программирования).Это может быть или не быть лучше, чем грубая сила.