TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1995

COGA 5-Wheel

Page Content

to Navigation

Preprints 1995

The complexity of Yamnitsky and Levin's simplices algorithm
Citation key Report-478-1995
Author Sven G. Bartels
Year 1995
Number 478
Institution Technische Universität Berlin, Institut für Mathematik
Abstract In 1982 Yamnitsky and Levin gave a variant of the ellipsoid method which uses simplices instead of ellipsoids. Unlike the ellipsoid method this simplices method can be implemented in rational arithmetic. We show, however, that this results in a non-polynomial method since the storage requirement may grow exponentially with the size of the input. Nevertheless, by introducing a rounding procedure we can guarantee polynomiality for both a central-cut and a shallow-cut version. Thus in most applications the simplices method can serve as a substitute for the ellipsoid method. In particular, it performs better than the ellipsoid method if it is used to obtain bounds for the volume of a convex body. Furthermore it can be used to estimate the optimal function value of total approximation problems.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe