<p>Computational Geometry is full of such examples. The main technique to address such problems is called parametric search - which is a rather non-trivial technique and too painful to explain. A classical "easy" example would be the problem of given a sorted matrix of size n by n (rows are sorted, and columns are sorted - say both in increasing order), output the smallest k number in the matrix. Clearly, given a value t, one can count in time $O(n)$, the number of entries in the matrix smaller than $t$ (hint - find the number of elements smaller than $t$ in the first row, and move to the next row, etc). A natural step would now to do a binary search over the values of t. For example, if you knew the values in the matrix are integers between $1$ and $O(n^3)$, this would yield an efficient algorithm to answering the original problem.</p>

CC BY-SA 3.0
2013-03-22T06:00:16.153Z
2013-03-22T06:00:16.153Z
Sariel Har-Peled
<p>Well the general condition is that you have a fitness function - a way to quantify the set of choices. If your decision problem is "best value for money" for some arbitrary definition of value, then your fitness function must evaluate the best according to the constraints. The evaluation of the best is then turned into the problem of optimizing (min/max) the fitness function over the set of choices.</p>

<p>If your decision problem for instance is: find the "shortest path from point A to B" in a 3D landscape, you could define the cost function as the distance from A-B. The decision problem is then turned into "minimize the cost of moving from A-B".</p>

<p>The optimizing algorithm may approach the problem in different ways, and usually there is some algo that suits the data structures best.</p>

<p>Another decision problem might be "is a given house prized relatively high or low on a given market". You could do some property analysis and derive a function of cost given house-size [sq-ft], number of rooms, price etc. You could then do some sort of linear regression over the data set. The problem of fitting a function to the data could be turned into a least squares problem.</p>

<p>I hope my answer helped clarify your questions. If not, please comment and I'll try to elaborate.</p>

CC BY-SA 3.0
2013-03-22T00:18:53.183Z
2013-03-22T00:18:53.183Z
Morten Jensen
<p>It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem.</p>

<p>I am looking for a few examples that show how this can be done, and explain this transformation.</p>

<p>I would like, though, examples which are practical. Meaning, the algorithm that solves the decision problem could actually turn into a practical algorithm for solving the corresponding optimization problem.</p>

<p>I know this is somewhat vague, but I can't think of a particular example -- that's what I am exactly looking for...</p>

<p>Any ideas?</p>

CC BY-SA 3.0
2013-03-22T03:38:46.653Z
This is not a **research-level** question in theoretical computer science.  Please see the [faq] for more information.
Jeffε
CC BY-SA 3.0
2013-03-22T04:25:32.557Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-03-22T07:16:19.287Z
ps: if you have read our [faq] and think the question is on topic on cstheory please edit the post and explain the motivation and background to show that it is research-level. Right now this seems a question from someone who is learning basic computability theory which means this question would be more suitable for [cs.se]. By the way, we also have a list of tips on how to how to write a better question which you can find in our [faq].
Kaveh
<computability><optimization>
how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?
poolk
# how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?

(Asked by: username_0 on 2013-03-21)

It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem.

I am looking for a few examples that show how this can be done, and explain this transformation.

I would like, though, examples which are practical. Meaning, the algorithm that solves the decision problem could actually turn into a practical algorithm for solving the corresponding optimization problem.

I know this is somewhat vague, but I can't think of a particular example -- that's what I am exactly looking for...

Any ideas?

**Tags:** computability, optimization
> **Comments:**
> **username_1**: This is not a **research-level** question in theoretical computer science.  Please see the [faq] for more information.  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  
> **username_2**: ps: if you have read our [faq] and think the question is on topic on cstheory please edit the post and explain the motivation and background to show that it is research-level. Right now this seems a question from someone who is learning basic computability theory which means this question would be more suitable for [cs.se]. By the way, we also have a list of tips on how to how to write a better question which you can find in our [faq].  

---

## 2 answers

### Answer by username_3 on 2013-03-22. Score: 1

Computational Geometry is full of such examples. The main technique to address such problems is called parametric search - which is a rather non-trivial technique and too painful to explain. A classical "easy" example would be the problem of given a sorted matrix of size n by n (rows are sorted, and columns are sorted - say both in increasing order), output the smallest k number in the matrix. Clearly, given a value t, one can count in time $O(n)$, the number of entries in the matrix smaller than $t$ (hint - find the number of elements smaller than $t$ in the first row, and move to the next row, etc). A natural step would now to do a binary search over the values of t. For example, if you knew the values in the matrix are integers between $1$ and $O(n^3)$, this would yield an efficient algorithm to answering the original problem.


---

### Answer by username_4 on 2013-03-22. Score: 0

Well the general condition is that you have a fitness function - a way to quantify the set of choices. If your decision problem is "best value for money" for some arbitrary definition of value, then your fitness function must evaluate the best according to the constraints. The evaluation of the best is then turned into the problem of optimizing (min/max) the fitness function over the set of choices.

If your decision problem for instance is: find the "shortest path from point A to B" in a 3D landscape, you could define the cost function as the distance from A-B. The decision problem is then turned into "minimize the cost of moving from A-B".

The optimizing algorithm may approach the problem in different ways, and usually there is some algo that suits the data structures best.

Another decision problem might be "is a given house prized relatively high or low on a given market". You could do some property analysis and derive a function of cost given house-size [sq-ft], number of rooms, price etc. You could then do some sort of linear regression over the data set. The problem of fitting a function to the data could be turned into a least squares problem.

I hope my answer helped clarify your questions. If not, please comment and I'll try to elaborate.


---

