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

Flow related doubt
Автор Zenkai, история, 6 лет назад, По-английски

Is there a well known trick in max-flow, in which after entering a node or edge the flow through it multiplies by some constant k, which can be different for each node. Something like described in the image above.

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

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

If you are just doing multiplications at each node rather than additions, you can just take the log of each weight and the problem is reduced to a normal max-flow. For example ln(a*k1) = ln(a)+ln(k1). So just solve the graph using logs, then your final answer e to the answer that you get from that process. (Though this of course introduces lots of rounding error and may not be acceptable for the application)

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

    But by this method, i think every time you have two or more incoming edges, their net flow will multiply instead of adding, eg log(a) + log(b) = log(ab).

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

      Ah, I was imagining finding 1 path at a time and then removing the used edges but I guess that general algorithms use augmenting paths, so having 2 incoming edges will be a problem. I'm not sure what you're talking about adding constant flow, unless you're talking about a different problem than max-flow... maybe I just don't understand the problem well enough without formal statement.

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

        For example in the above picture, whenever an incoming flow(say a) flows through an vertex, than outgoing flow is increased by by constant k and becomes(a+k)(only when a is non-zero). As you said the problem doesn't actually comes under max-flow statement since incoming flow != outgoing flow for a non source-sink vertex, but i was wondering if it could be converted into one, through some other modeling.

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

          Ok, I see what you mean more now. I don't think my method will work at all if addition is involved. I still am unclear about a few things of the statement though. Are we trying to maximize flow out of the source or into the sink? And when does constant flow get added? Is it just when you enter a node? Also, you say flow can be multiplied after entering a node or edge. One observation is that this is equivalent to just being multiplied after entering an edge (since we can just multiply the 'leaving a node' cost by the 'entering a node' cost).

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

    Besides, can you share how you add an extra constant flow, whenever you enter a node(say A), ofcourse we can add an extra edge from source to node but that would increase the flow by the constant k, even when netflow through A was 0 previously, but that is undesired in my case.

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

I believe not. Find another modeling.

→ Ответить