-
-
What is an algorithm?
-
-
-
Absolute Limitations on Algorithms
-
-
-
Resource limitations on algorithms
-
-
-
Divide and Conquer
-
Greedy
-
Landscapes
-
-
-
P versus NP
-
Building computers out of other problems
-
Unit Quiz
-
-
-
An algorithmic perspective on complex systems
-
-
-
Heuristics
-
Heuristics 2
-
Approximation algorithms
-
-
-
Randomized Algorithms I
-
Randomized Algorithms II
-
Randomized Algorithms III
-
Unit Quiz
-
-
7.2 Heuristics 2 » Quiz Explanation
1) The simplex algorithm shows that linear programming is in .
False - There are instances on which the simplex algorithm takes exponential time. In fact, it has been proved to be what is called "-mighty''. However, the smoothed analysis of Spielman and Teng shows that, on any input, we can modify the input by an arbitrarily small amount to find an instance on which the simplex algorithm runs in polynomial time.
2) The fact that linear programming is in P (which it is) does not show P = NP.
True - integer linear programming is NP-complete, but linear programming is not. A polynomial-time algorithm for integer linear programming would indeed show P=NP.
3) Approximation algorithms nd solutions that, while not optimal, look like the optimal solution.
Approximation algorithms only guarantee that the value being optimized will be within some factor of the optimum value. They do not guarantee that the solution they find looks anything like the optimal solution.