The continuous max flow problem is posed as follows :

sup $\int_\Omega p_s(x)dx$

subject to :

$|p(x)| \le C(x); \forall x \in \Omega $

$p_s(x) \le C_s(x); \forall x \in \Omega $

$p_t(x) \le C_t(x); \forall x \in \Omega $

$\nabla \cdot p(x) - p_s(x) + p_t(x) = 0; \forall x \in \Omega $

Here $p(x)$ is a field vector and is analogous to the flow in the discrete domain. $\nabla \cdot p$ is the divergence of the field p.

How do i find out the dual of this maximization problem using the lagrangian dual technique, i.e. the equivalent min cut formulation of the problem in the continuous domain.


Your question may be answered in the following paper:

@article{strang1983maximal, title={Maximal flow through a domain}, author={Strang, G.}, journal={Mathematical Programming}, volume={26}, number={2}, pages={123--143}, year={1983}, publisher={Springer} }

| cite | improve this answer | |
  • 1
    $\begingroup$ The paper does not take the approach that i want to follow. I believe that the dual can be obtained by simply finding the lagrangian function. I just did not know how to find the lagrangian dual function for the given function. I have now worked it out. $\endgroup$ – AnkurVj Jun 8 '11 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.