patternMinor
What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?
Viewed 0 times
thewhatpolynomialarelaterbutreducedexamplestimealgorithms
Problem
Arora-Barak says
It has also happened a few times that the first polynomial-time
algorithm for a problem had high complexity, say $n^{20}$, but soon
somebody simplified it to say an $n^5$ time algorithm
What are some examples of the above statement? I know AKS is one, are there any other?
It has also happened a few times that the first polynomial-time
algorithm for a problem had high complexity, say $n^{20}$, but soon
somebody simplified it to say an $n^5$ time algorithm
What are some examples of the above statement? I know AKS is one, are there any other?
Solution
Approximating volume of convex bodies
In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17.
a $O(n^{19})$ approximation algorithm was proposed.
The work of Lovász et al.: Simulated annealing in convex bodies and an $O^(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).
Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/
In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17.
a $O(n^{19})$ approximation algorithm was proposed.
The work of Lovász et al.: Simulated annealing in convex bodies and an $O^(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).
Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/
Context
StackExchange Computer Science Q#87073, answer score: 5
Revisions (0)
No revisions yet.