A polynomial-time algorithm for finding zero-sums

Erdös, Ginzburg and Ziv proved that any sequence of 2n−12n−1 (not necessary distinct) members of the cyclic group ZnZn contains a subsequence of length nn the sum of whose elements is congruent to zero modulo nn. There are several proofs of this celebrated theorem which combine combinatorial and algebraic ideas. Our main result is an alternative and constructive proof of this result. From this proof, we deduce a polynomial-time algorithm for finding a zero-sum nn-sequence of the given (2n−1)(2n−1)-sequence of an abelian group G with nn elements (a fortiori for ZnZn). To the best of our knowledge, this is the first efficient algorithm for finding zero-sum nn-sequences.