scientific article; zbMATH DE number 139625
[For the entire collection see Zbl 0745.00057.] The goal of this article is to present a selective introduction to the field of information-based complexity and to describe the seesaw nature of results in the last decade on the extent to which linear problems have linear optimal algorithms. The approach we take will certainly not do justice to the breadth of ideas, techniques, and applications that are coming into play in the general theory. Instead, we will take a direct route to the results on linear optimal algorithm, pausing occasionally to survey the pleasing way in which ideas from linear algebra and (functional) analysis are used. We mention some other theoretical and applied topics currently under investigation in the theory of optimal algorithms.
- Are linear algorithms always good for linear problems?
- Optimal algorithms for linear problems with Gaussian measures
- Linear problems (with extended range) have linear optimal algorithms
- Linearity of algorithms and a result of Ando
- Complexity of linear problems with a fixed output basis
- A decision procedure for linear ``big O equations
- Do Linear Problems Have Linear Optimal Algorithms?
- scientific article; zbMATH DE number 4141416 (Why is no real title available?)
- scientific article; zbMATH DE number 4161540 (Why is no real title available?)
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Can linear superiorization be useful for linear optimization problems?
- Noisy information for linear problems in the asymptotic setting
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4029604)
