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

min-cost-max-flow за n^3
Автор worms, 12 лет назад, По-русски

Ходят слухи, что min-cost-max-flow пишется за асимптотику n^3, а не n*m^2*logn. Верно ли это? Гугл не дает никакой информации по такому запросу. Подскажите пожалуйста настоящую асимптотику алгоритма и дайте ссылку на реализацию.

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

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

Если я не ошибаюсь, он работает за O(N^3) только на единичных сетях.

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

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

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

Часто величина max flow не превосходит N, а кратчайший путь на графе без отрицательных циклов можно искать за O(N2) алгоритмом Дейкстры. Тогда асимптотика будет как раз O(N3). Например, такая асимптотика верна при нахождении максимального паросочетания минимальной стоимости.

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

Ходят слухи что за nmlog(nC) книжка Ahuja.

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

    Это с единичными пропускными способностями, с помощью Cost scaling и проталкивания предпотока(push/relabel).

    ADD: Ссылка

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

      С единичными пропускными способностями можно в лоб Дейкстрой с потенциалами за O(n * m * log(n)) или O(n^3).

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

      страница 372. конец страницы если использовать динамические деревья то можно получить nmlogn и . а с wave оптимизацией n3log(nC)

      → Ответить