On Some Optimization Problems that Can Be Solved in O(n) Time
Conference Paper
(2021)
Research Group
Discrete Mathematics and Optimization
Copyright
© 2021 Y. Bai, C. Roos
DOI related publication
https://doi.org/10.1007/978-3-030-72040-7_4
To reference this document use:
https://resolver.tudelft.nl/uuid:47eaa99a-e6dc-4086-97f2-5d2b241f7823
More Info
expand_more
expand_more
Publication Year
2021
Language
English
Copyright
© 2021 Y. Bai, C. Roos
Research Group
Discrete Mathematics and Optimization
Bibliographical Note
Accepted author manuscript@en
Pages (from-to)
81-108
ISBN (print)
978-3-030-72039-1
ISBN (electronic)
978-3-030-72040-7
Reuse Rights
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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
License info not available