Complexity aspects of a semi-infinite optimization problem†

DOI10.1080/02331930701779013zbMath1134.65036OpenAlexW2134585965MaRDI QIDQ5449018

Klaus Meer

Publication date: 10 March 2008

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331930701779013

zbMATH Keywords

interval arithmeticcomplexity classessemi-infinite optimization

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Semi-infinite programming (90C34) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• New NP-hard and NP-complete polynomial and integer divisibility problems
• The polynomial-time hierarchy
• Separation of complexity classes in Koiran's weak model
• On the complexity of quadratic programming in real number models of computation
• Enclosing solutions of linear interval equations is NP-hard
• On a refined analysis of some problems in interval arithmetic using real number complexity theory
• Connections between generalized, inexact and semi-infinite linear programming
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines