  This paper initiates the study of the classic balanced graph partitioning
problem from an online perspective: Given an arbitrary sequence of pairwise
communication requests between $n$ nodes, with patterns that may change over
time, the objective is to service these requests efficiently by partitioning
the nodes into $\ell$ clusters, each of size $k$, such that frequently
communicating nodes are located in the same cluster. The partitioning can be
updated dynamically by migrating nodes between clusters. The goal is to devise
online algorithms which jointly minimize the amount of inter-cluster
communication and migration cost.
  The problem features interesting connections to other well-known online
problems. For example, scenarios with $\ell=2$ generalize online paging, and
scenarios with $k=2$ constitute a novel online variant of maximum matching. We
present several lower bounds and algorithms for settings both with and without
cluster-size augmentation. In particular, we prove that any deterministic
online algorithm has a competitive ratio of at least $k$, even with significant
augmentation. Our main algorithmic contributions are an $O(k
\log{k})$-competitive deterministic algorithm for the general setting with
constant augmentation, and a constant competitive algorithm for the maximum
matching variant.
