On Some Optimization Problems that Can Be Solved in O(n) Time

More Info
expand_more

Abstract

We consider nine elementary problems in optimization. We simply explore the conditions for optimality as known from the duality theory for convex optimization. This yields a quite straightforward solution method for each of these problems. The main contribution of this paper is that we show that even in the harder cases the solution needs only O(n) time.

Files

EasyProblems_2021_03_30.pdf
(pdf | 0.282 Mb)
- Embargo expired in 01-01-2023
Bai_Roos2021_Chapter_ONSomeOpt... (pdf)
(pdf | 0.445 Mb)

Download not available