Maximum flow problem with both minimum and maximum capacities
$begingroup$
I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$
A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow
However, I wasn't sure if this problem was exactly the same.
This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.
Thanks.
graph-theory algorithms
edited Apr 13 '17 at 12:32
Community♦
1
asked Nov 19 '14 at 6:52
FredFred
62
$endgroup$
add a comment |
$begingroup$
I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$
A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow
However, I wasn't sure if this problem was exactly the same.
This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.
Thanks.
graph-theory algorithms
edited Apr 13 '17 at 12:32
Community♦
1
asked Nov 19 '14 at 6:52
FredFred
62
$endgroup$
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52
add a comment |
$begingroup$
I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$
A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow
However, I wasn't sure if this problem was exactly the same.
This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.
Thanks.
graph-theory algorithms
edited Apr 13 '17 at 12:32
Community♦
1
asked Nov 19 '14 at 6:52
FredFred
62
$endgroup$
I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum $st$-flow where each edge $e$ has flow capacity $f(e)=0$ or $c_{min}<f(e)<c_{max}$
A search provided this possibility: https://cstheory.stackexchange.com/questions/16664/using-max-flow-ford-fulkerson-to-find-satisfying-flow
However, I wasn't sure if this problem was exactly the same.
This is a homework question. My intuition is to modify the Ford-Fulkerson method but I'm not sure how. Any hints would be greatly appreciated.
Thanks.
graph-theory algorithms
graph-theory algorithms
edited Apr 13 '17 at 12:32
Community♦
1
asked Nov 19 '14 at 6:52
FredFred
62
edited Apr 13 '17 at 12:32
Community♦
1
asked Nov 19 '14 at 6:52
FredFred
62
edited Apr 13 '17 at 12:32
Community♦
1
edited Apr 13 '17 at 12:32
Community♦
1
edited Apr 13 '17 at 12:32
Community♦
1
1
asked Nov 19 '14 at 6:52
FredFred
62
asked Nov 19 '14 at 6:52
FredFred
62
asked Nov 19 '14 at 6:52
FredFred
62
62
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52
add a comment |
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).
answered Nov 24 '14 at 3:50
ZenoZeno
1324
$endgroup$
add a comment |
$begingroup$
Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t,s}$.
There are many Min Cost Flow algorithms, see this link for example.
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1028853%2fmaximum-flow-problem-with-both-minimum-and-maximum-capacities%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).
answered Nov 24 '14 at 3:50
ZenoZeno
1324
$endgroup$
add a comment |
$begingroup$
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).
answered Nov 24 '14 at 3:50
ZenoZeno
1324
$endgroup$
add a comment |
$begingroup$
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).
answered Nov 24 '14 at 3:50
ZenoZeno
1324
$endgroup$
You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of $f(e)=0$ suggests), you can tell the algorithm to check for paths where $c_f(u,v) ge 0$, instead of $c_f(u,v) >0$ (as the Wikipedia article pseudocode states).
answered Nov 24 '14 at 3:50
ZenoZeno
1324
answered Nov 24 '14 at 3:50
ZenoZeno
1324
answered Nov 24 '14 at 3:50
ZenoZeno
1324
answered Nov 24 '14 at 3:50
ZenoZeno
1324
1324
add a comment |
add a comment |
$begingroup$
Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t,s}$.
There are many Min Cost Flow algorithms, see this link for example.
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
$endgroup$
add a comment |
$begingroup$
Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t,s}$.
There are many Min Cost Flow algorithms, see this link for example.
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
$endgroup$
add a comment |
$begingroup$
Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t,s}$.
There are many Min Cost Flow algorithms, see this link for example.
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
$endgroup$
Just finding a feasible flow will be a problem in itself. You are better off using a Min Cost Flow algorithm. Add an arc $(t,s)$, set all demands to $0$ and minimize $-x_{t,s}$.
There are many Min Cost Flow algorithms, see this link for example.
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
answered Nov 19 '17 at 21:16
A.G.A.G.
2,022711
2,022711
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1028853%2fmaximum-flow-problem-with-both-minimum-and-maximum-capacities%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What is your question? I suggest highlighting what you need so that others know what kind of answers you a looking for.
$endgroup$
– Joonas Ilmavirta
Nov 19 '14 at 7:07
$begingroup$
Replace "I'm trying to develop" with "What is" at the beginning of the first paragraph.
$endgroup$
– Fred
Nov 19 '14 at 7:52