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

Yanqin Bai; Kees Roos

doi:10.1007/978-3-030-72040-7_4

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

Yanqin Bai, Kees Roos^*

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

32 Downloads (Pure)

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.

Original language	English
Title of host publication	Numerical Analysis and Optimization, NAOV 2020
Editors	Mehiddin Al-Baali, Anton Purnama, Lucio Grandinetti
Place of Publication	Cham
Publisher	Springer
Pages	81-108
Number of pages	28
ISBN (Electronic)	978-3-030-72040-7
ISBN (Print)	978-3-030-72039-1
DOIs	https://doi.org/10.1007/978-3-030-72040-7_4
Publication status	Published - 2021
Event	5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020 - Muscat, Oman Duration: 6 Jan 2020 → 9 Jan 2020

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Volume	354
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Conference

Conference	5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020
Country/Territory	Oman
City	Muscat
Period	6/01/20 → 9/01/20

Bibliographical note

Accepted author manuscript

Keywords

Linear time methods
Optimality conditions
Optimization problems

Access to Document

10.1007/978-3-030-72040-7_4

EasyProblems 2021 03 30Accepted author manuscript, 206 KB

Cite this

@inproceedings{47eaa99ae6dc408697f25d2b241f7823,

title = "On Some Optimization Problems that Can Be Solved in O(n) Time",

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.",

keywords = "Linear time methods, Optimality conditions, Optimization problems",

author = "Yanqin Bai and Kees Roos",

note = "Accepted author manuscript; 5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020 ; Conference date: 06-01-2020 Through 09-01-2020",

year = "2021",

doi = "10.1007/978-3-030-72040-7_4",

language = "English",

isbn = "978-3-030-72039-1",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer",

pages = "81--108",

editor = "Mehiddin Al-Baali and Anton Purnama and Lucio Grandinetti",

booktitle = "Numerical Analysis and Optimization, NAOV 2020",

}

Bai, Y & Roos, K 2021, On Some Optimization Problems that Can Be Solved in O(n) Time. in M Al-Baali, A Purnama & L Grandinetti (eds), Numerical Analysis and Optimization, NAOV 2020. Springer Proceedings in Mathematics and Statistics, vol. 354, Springer, Cham, pp. 81-108, 5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020, Muscat, Oman, 6/01/20. https://doi.org/10.1007/978-3-030-72040-7_4

On Some Optimization Problems that Can Be Solved in O(n) Time. / Bai, Yanqin; Roos, Kees.
Numerical Analysis and Optimization, NAOV 2020. ed. / Mehiddin Al-Baali; Anton Purnama; Lucio Grandinetti. Cham: Springer, 2021. p. 81-108 (Springer Proceedings in Mathematics and Statistics; Vol. 354).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - Bai, Yanqin

AU - Roos, Kees

N1 - Accepted author manuscript

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Linear time methods

KW - Optimality conditions

KW - Optimization problems

UR - http://www.scopus.com/inward/record.url?scp=85121929939&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-72040-7_4

DO - 10.1007/978-3-030-72040-7_4

M3 - Conference contribution

AN - SCOPUS:85121929939

SN - 978-3-030-72039-1

T3 - Springer Proceedings in Mathematics and Statistics

SP - 81

EP - 108

BT - Numerical Analysis and Optimization, NAOV 2020

A2 - Al-Baali, Mehiddin

A2 - Purnama, Anton

A2 - Grandinetti, Lucio

PB - Springer

CY - Cham

T2 - 5th International Conference on Numerical Analysis and Optimization: Theory, Methods, Applications and Technology Transfer, NAOV 2020

Y2 - 6 January 2020 through 9 January 2020

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this