To the Steinitz lemma in coordinate form (Q1357729)

From MaRDI portal





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
    0 references
    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

    Identifiers