1
$\begingroup$

What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems remain feasible? Can one tell in advance?

I am particularly interested in scheduling problems and what to know as to how the uncertainty in information (e.g. processing times of jobs) affects the difficulty of the problems. I believe the problem becomes more difficult when information is uncertain. Is it true?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic_regulator

Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian_control

However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).

Improve this answer
$\endgroup$
2
  • $\begingroup$ How about combinatorial optimization problems, scheduling in particular? $\endgroup$ Commented Feb 13, 2018 at 3:57
  • 1
    $\begingroup$ I wish I knew anything about that! Looking forward to seeing other examples. $\endgroup$ Commented Feb 13, 2018 at 4:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.