[Computational Complexity] Cond. Cvg Sequences in R^d AND real applications!
- We present some PURE math that was APPLIED in a real way. I am more surprised by these things than I should be.
Recall that a summation &sumi=0&infin ai Conditionally Cvgs if it cvg but &sumi=0&infin |ai| does not cvg.
Recall the following theorem.
Cond Cvg Thm: Let &sumi=0&infin ai be a cond. cvg sum. Let A &isin R. Then there exists a way to rearrange the summation such that it cvg to A.What happens if instead of reals you have points in Rd? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)
Steinitz's Lemma Let d be a natural number, B be the unit ball in Rd, and V be a finite subset of B such that &sumv&isin V v = 0. Then there is an ordering v1, v2, ..., vn of the elements of V such thatThis can be used to show the following:
v1 &isin dB
v1+v2 &isin dB
v1+v2+v3 &isin dB
v1+...+vn &isin dB
End of Statement of Steinitz's Lemma
d-dim version of Cond Cvg Theorem If a1, a2, a3,... &isin Rd and &sumi=0&infin ai conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of Rd.
This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.
- A vector sum theorem and its application to improving flow shop guarantees. By I. Barany. Math. Oper. Res. Volume 6, 1981, 445-452. downloadhere or if it goes away or does not work then here
- Bibliography: Series of vectors and Riemann sums. By I. Halperin and T. Ando. Sapporo, Japan, 1989
- On approximate solutions of a scheduling problem. by S.V. Sevastyanov. Metody Diskr. Analiza Volume 32, 1978, 66-75. (In Russian).
- On some geometric methods in scheduling theory: a surey, Discrete Applied Math, Volume 55, 1994, 59-82.
Posted By GASARCH to Computational Complexity at 6/16/2009 08:57:00 AM