Why is the Ellipsoid Method of polynomial complexity?What is the “big-M” method? And are there two of...
How to understand payment due date for credit card?
How to save money by shopping at a variety of grocery stores?
Is it possible for a person to be tricked into becoming a lich?
Do application leftovers have any impact on performance?
Is the Amazon rainforest the "world's lungs"?
How to investigate an unknown 1.5GB file named "sudo" in my Linux home directory?
Under GDPR, can I give permission once to allow everyone to store and process my data?
How can I reply to coworkers who accuse me of automating people out of work?
Give Lightning Web Component a Prettier Name
Is it recommended to point out a professor's mistake during their lecture?
Create a list of snaking numbers under 50,000
What is the sound/audio equivalent of "unsightly"?
Could a complex system of reaction wheels be used to propel a spacecraft?
Don't look at what I did there
Why didn't Doc believe Marty was from the future?
RAID0 instead of RAID1 or 5, is this crazy?
Do universities maintain secret textbooks?
In what language did Túrin converse with Mím?
How to handle inventory and story of a player leaving
How can I fix cracks between the bathtub and the wall surround?
Defending Castle from Zombies
Why does Sauron not permit his followers to use his name?
Historical Daf Yomi calendar
What is this "opened" cube called?
Why is the Ellipsoid Method of polynomial complexity?
What is the “big-M” method? And are there two of them?Why is it important to choose big-M carefully and what are the consequences of doing it badly?Assignment problem using Hungarian methodAre there any efficient algorithms to solve the longest path problem in networks with cycles?When is the original BFGS algorithm still better than the Limited-Memory version?Polynomially solvable problems with exponential extension complexityDoes the problem of P vs NP come under the category of Operational Research?State-of-the-art algorithms for solving linear programsFind feasible point in polynomial time in linear programming
$begingroup$
We know that the ellipsoid method is proven to be of polynomial complexity.
However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no solution exists), which results in a non-polynomial amount of calculations, which is the method is inefficient in practice.
Is the method considered polynomial simply because we measure P-hardness as a function of the number of variables, or is there also a polynomial bound on the number of constraints that we need to add?
linear-programming computational-complexity
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
We know that the ellipsoid method is proven to be of polynomial complexity.
However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no solution exists), which results in a non-polynomial amount of calculations, which is the method is inefficient in practice.
Is the method considered polynomial simply because we measure P-hardness as a function of the number of variables, or is there also a polynomial bound on the number of constraints that we need to add?
linear-programming computational-complexity
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago
add a comment |
$begingroup$
We know that the ellipsoid method is proven to be of polynomial complexity.
However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no solution exists), which results in a non-polynomial amount of calculations, which is the method is inefficient in practice.
Is the method considered polynomial simply because we measure P-hardness as a function of the number of variables, or is there also a polynomial bound on the number of constraints that we need to add?
linear-programming computational-complexity
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
We know that the ellipsoid method is proven to be of polynomial complexity.
However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no solution exists), which results in a non-polynomial amount of calculations, which is the method is inefficient in practice.
Is the method considered polynomial simply because we measure P-hardness as a function of the number of variables, or is there also a polynomial bound on the number of constraints that we need to add?
linear-programming computational-complexity
linear-programming computational-complexity
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
edited 4 hours ago
LarrySnyder610♦
5,80214 silver badges64 bronze badges
5,80214 silver badges64 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
nikazanikaza
83510 bronze badges
asked 9 hours ago
nikazanikaza
83510 bronze badges
83510 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago
add a comment |
1
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago
1
1
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.
Consider a linear program. That is, we want to minimize a linear function over a polyhedron.
Bounding the polyhedron
If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.
Observation
Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.
Center of gravity method
The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- Repeat Steps 1 and 2 until the current polytope is small.
Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.
There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.
Ellipsoid method
The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- Repeat Steps 1 to 3 until the current ellipsoid is small.
In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.
In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!
As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.
Final thoughts
Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.
$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "700"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
nikaza is a new contributor. Be nice, and check out our Code of Conduct.
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%2for.stackexchange.com%2fquestions%2f1423%2fwhy-is-the-ellipsoid-method-of-polynomial-complexity%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.
Consider a linear program. That is, we want to minimize a linear function over a polyhedron.
Bounding the polyhedron
If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.
Observation
Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.
Center of gravity method
The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- Repeat Steps 1 and 2 until the current polytope is small.
Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.
There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.
Ellipsoid method
The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- Repeat Steps 1 to 3 until the current ellipsoid is small.
In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.
In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!
As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.
Final thoughts
Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.
$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
$endgroup$
add a comment |
$begingroup$
The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.
Consider a linear program. That is, we want to minimize a linear function over a polyhedron.
Bounding the polyhedron
If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.
Observation
Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.
Center of gravity method
The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- Repeat Steps 1 and 2 until the current polytope is small.
Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.
There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.
Ellipsoid method
The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- Repeat Steps 1 to 3 until the current ellipsoid is small.
In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.
In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!
As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.
Final thoughts
Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.
$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
$endgroup$
add a comment |
$begingroup$
The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.
Consider a linear program. That is, we want to minimize a linear function over a polyhedron.
Bounding the polyhedron
If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.
Observation
Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.
Center of gravity method
The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- Repeat Steps 1 and 2 until the current polytope is small.
Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.
There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.
Ellipsoid method
The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- Repeat Steps 1 to 3 until the current ellipsoid is small.
In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.
In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!
As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.
Final thoughts
Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.
$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
$endgroup$
The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.
Consider a linear program. That is, we want to minimize a linear function over a polyhedron.
Bounding the polyhedron
If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.
Observation
Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.
Center of gravity method
The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- Repeat Steps 1 and 2 until the current polytope is small.
Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.
There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.
Ellipsoid method
The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- Repeat Steps 1 to 3 until the current ellipsoid is small.
In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.
In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!
As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.
Final thoughts
Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.
$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
edited 3 hours ago
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
answered 5 hours ago
Kevin DalmeijerKevin Dalmeijer
2,4345 silver badges29 bronze badges
2,4345 silver badges29 bronze badges
add a comment |
add a comment |
nikaza is a new contributor. Be nice, and check out our Code of Conduct.
nikaza is a new contributor. Be nice, and check out our Code of Conduct.
nikaza is a new contributor. Be nice, and check out our Code of Conduct.
nikaza is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Operations Research 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%2for.stackexchange.com%2fquestions%2f1423%2fwhy-is-the-ellipsoid-method-of-polynomial-complexity%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
1
$begingroup$
Yes, the ellipsoid method runs in polynomial time when applied to LPs. (Polynomial time refers to the number of basic computer calculations.) I do not understand your comment about adding feasibility cuts. (Are you confusing the ellipsoid method and the cutting plane method?) What does P-hardness have to do with this?
$endgroup$
– Austin Buchanan
6 hours ago