𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension

✍ Scribed by Bernard Chazelle; Jiřı́ Matoušek

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
208 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We show that with recently developed derandomization techniques, one can convert Clarkson's randomized algorithm for linear programming in fixed dimension into a linear-time deterministic algorithm. The constant of proportionality is d O Ž d . , which is better than those for previously known algorithms. We show that the algorithm works in a fairly general abstract setting, which allows us to solve various other problems, e.g., computing the minimum-volume ellipsoid enclosing a set of n points and finding the maximum volume ellipsoid in the intersection of n halfspaces.

📜 SIMILAR VOLUMES

Optimal timing of observations for state
Optimal timing of observations for state estimation in a one-dimensional linear continuous system
✍ Shogo Tanaka; Tsuyoshi Okita 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 288 KB

This paper considers the optimal timing of observations for the state estimation in a one-dimensional linear continuous stochastic system which is corrupted by white Gaussian noise. The criterion adopted ia a min-max one. The optimal observation times are analytically shown to be located periodicall