To the Steinitz lemma in coordinate form (Q1357729)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: To the Steinitz lemma in coordinate form |
scientific article; zbMATH DE number 1021677
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | To the Steinitz lemma in coordinate form |
scientific article; zbMATH DE number 1021677 |
Statements
To the Steinitz lemma in coordinate form (English)
0 references
26 August 1997
0 references
We consider an arbitrary finite family of vectors in \(m\)-dimensional space with sum zero and the absolute value of any vector's coordinate at most 1. We prove that there exists an order of vector summation for this family such that every partial sum has the absolute value of the first coordinate at most 1 while the other coordinates are bounded by a constant at most \(O(m^{3/2})\). We also describe a polynomial-time algorithm which computes an order of vector summation for which all partial sums meet somewhat weaker bounds (at most \(O(m^2)\)) on the absolute value of coordinates from 2 to \(m\). (The absolute value of the first coordinate still remains at most 1.).
0 references
vector summation
0 references
Steinitz constant
0 references
polynomial-time algorithm
0 references