Optimal enclosure of quadratic interval functions

DOI10.1023/A:1024415715798MaRDI QIDQ1276128zbMATH OpenOpenAlexFDO

Authors Misha Koshelev, Luc Longpré, Patrick Taillibert

Publication date 30 March 1999

Published in Reliable Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1024415715798

zbMATH Keywords

algorithmcomputational complexityinterval enclosureinterval polynomialsNP-hardoptimal linear enclosurequadratic interval function

Mathematics Subject Classification ID

Interval and finite arithmetic (65G30) Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The authors show that the computation of the optimal linear enclosure of a given quadratic interval function of \(n\) variables is NP-hard. An efficient algorithm is proposed in the case \(n=1\).

Recommendations

• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 869739
• Linear interval equations: Computing enclosures with bounded relative or absolute overestimation is NP-hard
• Enclosing solutions of linear interval equations is NP-hard
• On a refined analysis of some problems in interval arithmetic using real number complexity theory

Cited in

(3)

• Optimal interval enclosures for fractionally-linear functions, and their application to intelligent control
• scientific article; zbMATH DE number 2064520 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003

Describes a project that uses

Uses Software

• INTOPT_90

This page was built for publication: Optimal enclosure of quadratic interval functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1276128)