Algorithms that still produce a solution (maybe not optimal) even when interrupted: Shary's idea justified (Q1383750)

Interval algorithms are usually designed to yield an enclosure, i.e. a superset, of the solution set in question (ideally, the narrowest one). This papers deals with algorithms that produce an enclosure of the solution set at any intermediate stage. The idea of such algorithms, ascribed here to \textit{S. P. Shary} [SIAM J. Numer. Anal. 32, No. 2, 610-630 (1995; Zbl 0838.65023)], goes in fact back to mathematical programming (primal methods as opposed to dual ones). The main result of this paper says, roughly speaking, that each interval algorithm can be converted into an interval algorithm possessing the above property such that the computational time still increases only linearly.