Блог пользователя always_first

Задача оптимизации в таблице
Автор always_first, история, 9 лет назад, По-русски

Всем привет!

Недавно я ознакомился с венгерским алгоритмом решения задачи о назначениях. Мне стало любопытно, можно ли за полиномиальное время решить более общий случай: в таблице n × m выбрать числа таким образом, что сумма выбранных чисел была максимальна, причем в каждой строке были выбраны не менее Rmin и не более Rmax чисел, а в каждом столбце были выбраны не менее Cmin и не более Cmax чисел.

При Rmin = Rmax = 1 и Cmin = Cmax = 1 это задача о назначениях. А что можно сказать о более общем случае? Есть ли у вас какие-то мысли по этому поводу (может быть, хотя бы в более частном случае Rmin = Rmax = R и Cmin = Cmax = C)? Буду благодарен любым идеям.

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been translated by always_first (original revision, translated revision, compare)

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In the case Rmin = Rmax = Cmin = 1, and general Cmax the problem reduces to Generalized assignment problem, which is NP-hard (and hard to approximate). I don't expect it to get any easier for general values of the bounds.

However, this kind of problems are usally simple to transform to Integer Program, so if you're instance is not big you can hope to get an exact solution using a good MIP solver

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Reduction is not correct since the problem you mentioned has a more strong weight constraint: "sum of costs of tasks cannot exceed the budget of an agent". In our case all weights in this constraint are equal to 1.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Пара тривиальных наблюдений:

  1. Задача о назначениях — это Rmin = 0, а не Rmin = 1 (или симметрично с C).

  2. Rmin  =  Rmax  =  R и Cmin  =  Cmax  =  C — это взять всю таблицу.

Может быть, решаемая (за полином) задача получится при Rmin = 0 и Rmax = 2?..

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Да, это Вы, конечно, правы. Rmin = Rmax = 1 — это для случая квадратной таблицы (n = m).
    2. Имелось в виду, что 1 ≤ R ≤ n, 1 ≤ C ≤ m — произвольные числа.
    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Isn't it a simple minimum cost LR-flow problem? Consider the classical bipartite graph where rows correspond to the left part and columns correspond to the right part, and there exist edges 

(r -> c, cost = A[r][c], 0 <= flow <= 1)    for each row r, column c
(s -> r, cost = 0, R_min <= flow <= R_max)  for each row r
(c -> t, cost = 0, C_min <= flow <= C_max)  for each column c
→ Ответить