Applications of Network Flow
Circulation with Demands
Given:
- Graph G(V,E)
- Capacities on the edges
- Demands for each vertex {d_v} such that
- d_v > 0 \implies Net flow into vertex (Source)
- d_v < 0 \implies Net flow out of vertex (Sink)
- d_v = 0 \implies Inflow equals outflow (Normal Node)
Definition: Circulation
Circulation is a function f: E \rightarrow \mathbb{R}^+ which satisfies the following
- Bounded by capacity: f(e) \leq c(e)
- Conservation condition: f^{in}(v) - f^{out}(v) = d_v
Lemma: Necessary condition for Feasible circulation \rightarrow \sum_v d_v = 0
Proof:
\begin{align} \sum_v d_v & = \sum_v f^{in}(v) - f^{out}(v) \\ & = \sum_v f^{in}(v) - \sum_v f^{out}(v) \\ & = 0 \end{align}
Since flow on every edge appears twice once as inflow on a vertex and other time as outflow on the other vertex on that edge.
In other words, there is a feasible solution only if D = \sum_{v>0}d_v = \sum_{v<0} {- d_v}
Algorithm: Finding Circulation
- Check necessity condition
- Connect all vertices with d_v < 0 to a super source via edges with capacity -d_v
- Connect all vertices with d_v > 0 to a super source via edges with capacity d_v
- On this flow network H, compute max-flow
- If flow value is D, then we have a valid circulation
- Else, circulation is infeasible
Correctness:
If there is a valid circulation in G, then in H there is a s-t max flow with value D obtained by pushing full capacities from source to the vertices with negative demand.
Conversely, a max-flow with value D in H is possible only when full capacities of the subordinate sources are used which implies that both capacity constraint and conservation condition are maintained. Hence there is a valid circulation in G.
Circulation with Demands and Lower bounds
Given:
- Graph G(V,E)
- Capacities on the edges
- Demands for each vertex {d_v}
- Lower bound for each edge \ni l(e) \leq c(e)
Now, a valid circulation is one where l(e) \leq f(e) \leq c(e).
Algorithm: Get rid of the lower bound somehow and then solve the circulation with demands
- Push a flow equal to the lower bound on each edge
- It satisfies the bounds
- Does not satisfy the conservation of flow
- Let L_v = f^{in}(v) - f^{out}(v) be the residual demand
- Set the new d'_v = d_v - L_v and reduce the capacities to c'(e) = c(e) - l(e) to get new graph G'
- The lower bounds vanish
- Solve the circulation problem in G'
- Add the circulation to the lower bounds f = f_0 + f'
Correctness:
Want to show that G has valid circulation with demands and lower bounds if and only if G' has a valid circulation with demands.
First we show, (f \text{ is valid } \implies f' \text{ is valid } )
- f(e) - l(e) \leq c(e) - l(e) \implies f'(e) \leq c'(e) \rightarrow hence bounded by capacity
- \sum_{e \; into \; v } (f(e) - l(e)) - \sum_{e \; out \; of \; v} (f(e) - l(e)) = d_v - L_v \rightarrow hence flow is conserved
Now we show, (f '\text{ is valid } \implies f \text{ is valid } )
- Clearly l(e) \leq f_0(e) + f'(e) \leq l(e) + c'(e) = c(e) \rightarrow hence satisfies the bounds
- \sum_{e \; into \; v } (l(e) + f'(e)) - \sum_{e \; out \; of \; v} (l(e) + f'(e)) = L_v + (d_v - L_v) = d_v \rightarrow hence the flow is conserved
Hence proved.
Survey Design
Problem Statement:
Given:
- Set of consumers
- Set of products
- List of products that each consumer has consumed
Want:
- To ask questions to the consumer about a subset of the products that the consumer used
- i^{th} consumer would answer only questions in the range [c_i, c'_i]
- For the i^{th} product we want to ask question in the range [p_i, p'_i]
Question:
How to assign questions to the consumers so that we get required information about each product while keeping the consumers happy?
Algorithm:
- Form a Bipartite graph with consumers on one side and products on the other
- Connect the consumers with the products that they used by an edge with capacity 1
- Connect the consumers to a source S with edges of capacities with lower (c_i) and upper (c'_i) bound
- Connect the products to a sink T with edges of capacities with lower (p_i) and upper (p'_i) bound
- We want to get a flow from S to T
- But we only know how to compute a circulation
- So connect T to S by an edge of infinite capacity
- Demands on all the vertices including source and sink is 0
- Happily compute a circulation with lower bounds on this network
Time Complexity:
- n consumers
- u products
- m \leftarrow sum of the number of products used by the consumers
- |E| = m
- |V| = n + u
- O(|V||E|^2) = O((n+u) m^2)
Circulation with Demands
Given:
- Graph G(V,E)
- Capacities on the edges
- Demands for each vertex {d_v} such that
- d_v > 0 \implies Net flow into vertex (Source)
- d_v < 0 \implies Net flow out of vertex (Sink)
- d_v = 0 \implies Inflow equals outflow (Normal Node)
Definition: Circulation
Circulation is a function f: E \rightarrow \mathbb{R}^+ which satisfies the following
- Bounded by capacity: f(e) \leq c(e)
- Conservation condition: f^{in}(v) - f^{out}(v) = d_v
Lemma: Necessary condition for Feasible circulation \rightarrow \sum_v d_v = 0
Proof:
\begin{align} \sum_v d_v & = \sum_v f^{in}(v) - f^{out}(v) \\ & = \sum_v f^{in}(v) - \sum_v f^{out}(v) \\ & = 0 \end{align}
Since flow on every edge appears twice once as inflow on a vertex and other time as outflow on the other vertex on that edge.
In other words, there is a feasible solution only if D = \sum_{v>0}d_v = \sum_{v<0} {- d_v}
Algorithm: Finding Circulation
- Check necessity condition
- Connect all vertices with d_v < 0 to a super source via edges with capacity -d_v
- Connect all vertices with d_v > 0 to a super source via edges with capacity d_v
- On this flow network H, compute max-flow
- If flow value is D, then we have a valid circulation
- Else, circulation is infeasible
Correctness:
If there is a valid circulation in G, then in H there is a s-t max flow with value D obtained by pushing full capacities from source to the vertices with negative demand.
Conversely, a max-flow with value D in H is possible only when full capacities of the subordinate sources are used which implies that both capacity constraint and conservation condition are maintained. Hence there is a valid circulation in G.
Circulation with Demands and Lower bounds
Given:
- Graph G(V,E)
- Capacities on the edges
- Demands for each vertex {d_v}
- Lower bound for each edge \ni l(e) \leq c(e)
Now, a valid circulation is one where l(e) \leq f(e) \leq c(e).
Algorithm: Get rid of the lower bound somehow and then solve the circulation with demands
- Push a flow equal to the lower bound on each edge
- It satisfies the bounds
- Does not satisfy the conservation of flow
- Let L_v = f^{in}(v) - f^{out}(v) be the residual demand
- Set the new d'_v = d_v - L_v and reduce the capacities to c'(e) = c(e) - l(e) to get new graph G'
- The lower bounds vanish
- Solve the circulation problem in G'
- Add the circulation to the lower bounds f = f_0 + f'
Correctness:
Want to show that G has valid circulation with demands and lower bounds if and only if G' has a valid circulation with demands.
First we show, (f \text{ is valid } \implies f' \text{ is valid } )
- f(e) - l(e) \leq c(e) - l(e) \implies f'(e) \leq c'(e) \rightarrow hence bounded by capacity
- \sum_{e \; into \; v } (f(e) - l(e)) - \sum_{e \; out \; of \; v} (f(e) - l(e)) = d_v - L_v \rightarrow hence flow is conserved
Now we show, (f '\text{ is valid } \implies f \text{ is valid } )
- Clearly l(e) \leq f_0(e) + f'(e) \leq l(e) + c'(e) = c(e) \rightarrow hence satisfies the bounds
- \sum_{e \; into \; v } (l(e) + f'(e)) - \sum_{e \; out \; of \; v} (l(e) + f'(e)) = L_v + (d_v - L_v) = d_v \rightarrow hence the flow is conserved
Hence proved.
Survey Design
Problem Statement:
Given:
- Set of consumers
- Set of products
- List of products that each consumer has consumed
Want:
- To ask questions to the consumer about a subset of the products that the consumer used
- i^{th} consumer would answer only questions in the range [c_i, c'_i]
- For the i^{th} product we want to ask question in the range [p_i, p'_i]
Question:
How to assign questions to the consumers so that we get required information about each product while keeping the consumers happy?
Algorithm:
- Form a Bipartite graph with consumers on one side and products on the other
- Connect the consumers with the products that they used by an edge with capacity 1
- Connect the consumers to a source S with edges of capacities with lower (c_i) and upper (c'_i) bound
- Connect the products to a sink T with edges of capacities with lower (p_i) and upper (p'_i) bound
- We want to get a flow from S to T
- But we only know how to compute a circulation
- So connect T to S by an edge of infinite capacity
- Demands on all the vertices including source and sink is 0
- Happily compute a circulation with lower bounds on this network
Time Complexity:
- n consumers
- u products
- m \leftarrow sum of the number of products used by the consumers
- |E| = m
- |V| = n + u
- O(|V||E|^2) = O((n+u) m^2)
No comments:
Post a Comment