学术文献库

We study connections between expansion in bipartite graphs and efficient online matching modeled via several games. In the basic game, an opponent switches {\em on} and {\em off} nodes on the left side and, at any moment, at most $K$ nodes may be on. Each time a node is switched on, it must be irrevocably matched with one of its neighbors. A bipartite graph has $e$-expansion up to $K$ if every set $S$ of at most $K$ left nodes has at least $e\#S$ neighbors. If all left nodes have degree $D$ and $e$ is close to $D$, then the graph is a lossless expander. We show that lossless expanders allow for a polynomial time strategy in the above game, and, furthermore, with a slight modification, they allow a strategy running in time $O(D \log N)$, where $N$ is the number of left nodes. Using this game and a few related variants, we derive applications in data structures and switching networks. Namely, (a) 1-query bitprobe storage schemes for dynamic sets (previous schemes work only for static sets),(b) explicit space- and time-efficient storage schemes for static and dynamic sets with non-adaptive access to memory (the first fully dynamic dictionary with non-adaptive probing using almost optimal space), and (c) non-explicit constant depth non-blocking $N$-connectors with poly$(\log N)$ time path finding algorithms whose size is optimal within a factor of $O(\log N)$ (previous connectors are double-exponentially slower).