Let's say I had an optimization problem

$$ \min_{x \in D} f(x) $$

Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.

Imagine I had a polynomial time algorithm that - given $f$ - could provide me with an interval for the optimal objective function value $f^*$ using finite numbers $LBD$ and $UBD$ where $LBD < f^* \leq UBD$.

Could I use this to show that the $\epsilon$-evaluation problem can be solved in polynomial time? Here the $\epsilon$-evaluation problem is a problem that for any $\epsilon > 0$ finds a real number $z$ such that $f^* \leq z \leq f^* + \epsilon$.

For the purposes of this problem, we can assume that I have a computer that can store real numbers and perform exact elementary operations with them.

  • $\begingroup$ You need to be more clear about what you mean by "upper bound recognition problem". Is it: given $l\leq u$, decide if $l \leq f^* \leq u$? Also you should specify the model of computation, is it the Real-RAM (= BSS) model? (if the answer to these is yes then you can efficiently find $f^*$ using binary search). $\endgroup$
    – Kaveh
    Commented Mar 10, 2011 at 11:03

1 Answer 1


The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.

I'm handwaving a lot, because parametric search is quite complicated. This survey talks about ways of making it practical, and also has a decent explanation of the basic idea. This older survey gives a number of examples of parametric search.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.