Return to Question

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$

where $f(1, 2)$ denotes the flow through arc $(1, 2)$.

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$

where $f(1, 2)$ denotes the flow through arc $(1, 2)$.

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

2 * f(1, 2) + 3 * f(4, 5) + f(3, 7) <= 10,

where f(1, 2) denotes the flow through arc (1, 2).

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a * f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$

where $f(1, 2)$ denotes the flow through arc $(1, 2)$.

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

2 * f(1, 2) + 3 * f(4, 5) + f(3, 7) <= 10,

where f(1, 2) denotes the flow through arc (1, 2).

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

2 * f(1, 2) + 3 * f(4, 5) + f(3, 7) <= 10,

where f(1, 2) denotes the flow through arc (1, 2).

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a * f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.