Соответствие максимального веса (MWM) для предварительно определенного количества узлов

Question

Мне дан взвешенный график, и я хочу найти набор ребер, чтобы каждый узел падал только на одно ребро и чтобы сумма выбранных весов ребер была максимизирована.Насколько я знаю, эту проблему обычно называют сопоставлением с максимальным весом, и существуют быстрые приближения для нее: https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf

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

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

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

Answer 1

Некоторые мысли.

1. Жадный алгоритм для этой задачи - 2-приближение.Представьте, что во время выполнения жадного алгоритма мы сохраняем счет в сравнении с оптимальным решением следующим образом.Каждый раз, когда мы добавляем ребро в жадное решение, мы удаляем падающие ребра в оптимальном решении, которое, как я утверждаю, должно иметь вес, не превышающий жадное ребро.Если ни одно ребро не будет удалено из оптимального решения, вместо этого мы удаляем два самых тяжелых ребра, которые, как я утверждаю, должны иметь вес не больше жадного ребра.Поскольку жадное решение должно иметь как минимум вдвое меньше ребер, чем оптимальное решение, я утверждаю, что на конце не осталось оптимальных ребер, и, следовательно, жадность - это 2-приближение, потому что мы никогда не удаляли более 2х веса с каждым жадным ребром.

2. Полный граф из 20 000 вершин находится прямо на той линии, где я не знаю, будет ли целочисленное программирование хорошей идеей.Я думаю, что все еще стоит попробовать, потому что это достаточно просто.

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