Solving Continuous Problems with Discrete Algorithms and Best Possible Results

We discuss an impossibility result (Hochbaum 1994) that establishes that there is no strongly polynomial algorithm for any non-linear, non-quadratic, optimization problem. One implication of the result is that the complexity of "solving" continuous problems is only defined for discrete algorithms. We illustrate the use of this result in two contexts. One is for the Markov Random Fields in image segmentation, and the other is the statistical model of isotonic regression and some of its generalizations. For these problems we will describe the best possible polynomial time algorithms which are based on combinatorial optimization.