COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2012

We work with small size balanced subsets of Z_p when p is prime. In a balanced set S, each element x in S is a midpoint between two other elements from S, i.e. 2x=y+z (mod p), y, z in S\{x}. Denote the minimum cardinality of a balanced set modulo p by α(p). We prove a new lower bound for α(p): for every prime p > 2, α(p) >= log₂ (p) + 1.41. Small balanced sets are needed in strategies for the family of combinatorial games analyzed in several papers by Z. Nedev and A. Quas.

We construct a new proximity graph, called the Pie Delaunay graph, on a set of n points which is a super graph of YG and Euclidean minimum spanning tree (EMST). We efficiently maintain the PDG where the points are moving in the plane. We use the kinetic PDG to create a kinetic data structure (KDS) for maintenance of the YG and the EMST on a set of n moving points in 2-dimensional space. Assuming x and y coordinates of the points are defined by algebraic functions of at most degree s, the structure uses O(n) space, O(n log n) preprocessing time, and processes O(n²λ_2s+2(sn) β_s+2(n)) events for the YG and O(n²λ_2s+2(sn)) events for the EMST, each in O(log² n) time. Here, λ_s(n) = nβ_s(n) is the maximum length of Davenport-Schinzel sequences of order s on n symbols.

Our KDS processes nearly cubic events for the EMST which improves the previous bound O(n⁴) by Rahmati et al.

Previous Talks

A solution to Wilf's sigma tau problem
Aaron Williams
Department of Mathematics and Statistics, McGill University
Friday Feb. 24, 2:30-3:30pm, ECS 660

The symmetric group S(n) can be generated by two simple operations: A rotation σ = (1 2 ... n), and a swap τ = (1 2). In 1975, Herb Wilf (1931-2012) asked if a stronger result holds: Can S(n) can be sequenced "so that each is obtained from its predecessor" by σ or τ? For example,

Don Knuth rates Wilf's problem as the second most difficult open problem in his new volume of The Art of Computer Programming, and states that solutions may not be of practical value due to their complexity. In this talk we solve the sigma tau problem by constructing a cyclic solution when n is odd, and a non-cyclic solution when n is even. (This is best possible, since a campanological result by Rankin and Swan proves there are no cyclic solutions when n is even.) The construction leads to a simple algorithm that creates each successive permutation in O(1) amortized time.

Short-range communication devices have enabled the large-scale dissemination of information through user mobility and contact, without the assistance of communication infrastructures. However, the intermittent connectivity, makes it challenging to determine when and how to forward a message possibly through a series of third parties to deliver it to the destination. This problem has attracted a lot of attention in the literature lately, with proposals ranging from oblivious epidemic to context-aware schemes. However most existing work assumed either independent or identical mobility characteristic across the users population. Observing most human mobility and interaction are interest-driven in the real world, in this research, we evaluate the performance of these schemes with an interest-driven mobility model. We further propose to take the user interest into account when determining routing strategies to further improve the performance of these schemes for mobile social networks. Simulation results have demonstrated the efficacy of the interest-aware routing strategies.