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

Conference paper (2021)

Authors

Y. Bai Shanghai University
C. Roos Discrete Mathematics and Optimization - EEMCS
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2021 Y. Bai, C. Roos
DOI: https://doi.org/10.1007/978-3-030-72040-7_4
Linear time methods Optimality conditions Optimization problems
More Info
expand_more

Published Date

2021

Language

English

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.