Optimally listing of subsets Suppose I have a collection of $m$ subsets of $\{1,\dots,n\}$, all of size $k$. I want to list these subsets so that two subsets adjacent to one another in the list are as close to one another as possible in that their intersection is as small in cardinality as possible. Can I do this in $o(m^2)$ time?
Without knowing any further restrictions on the parameters, the problem is NP-hard.

Let $G = (V,E)$ be an undirected graph. For $v \in V$, define the set $S_v = \{ e \mid e \in E \mbox{ is incident to } v\}$. Then $| S_u \cap S_v | = 1$ if $u$ and $v$ are adjacent, and $|S_u \cap S_v| = 0$ otherwise. You can pad out each $S_v$ with distinct junk items until each set has the same size. Then an ordering of $\{ S_v \mid v \in V\}$ in which adjacent sets have "as large an intersection as possible" corresponds to a Hamiltonian path in $G$ (for sensible measures like maximizing $\sum_i |S_i \cap S_{i+1}|$ or maximizing $\min_i |S_i \cap S_{i+1}|$).

If you want adjacent sets to have "as small an intersection as possible", simply complement each of these sets and the same reduction also works.

Your question suggests that you think this problem can be done in $O(m^2)$, and now I'm curious why.