Optimization with pattern-avoiding input

Permutation pattern-avoidance is a central concept of both enumerative and extremal combinatorics. We study the effect of permutation pattern-avoidance on the complexity of optimization problems.

In the context of the dynamic optimality conjecture (Sleator, Tarjan, STOC 1983), Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak (FOCS 2015) conjectured that the amortized search cost of an optimal binary search tree (BST) is constant whenever the search sequence is pattern-avoiding, in contrast to the \(\Theta(\log{n})\) cost in the general case. The best known bound to date is \(2^{\alpha{(n)}(1+o(1))}\) recently obtained by Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024); here \(n\) is the BST size and \(\alpha(\cdot)\) the inverse-Ackermann function. We resolve the conjecture, showing a tight \(O(1)\) bound. This indicates a barrier to dynamic optimality: any candidate online BST (e.g., splay trees or greedy trees) must match this optimum, but current analysis techniques only give superconstant bounds.

More broadly, we argue that the easiness of pattern-avoiding input is a general phenomenon, not limited to BSTs or even to data structures. To illustrate this, we show that when the input avoids an arbitrary, fixed, a priori unknown pattern, one can efficiently compute:

• a traveling salesman tour of \(n\) points from a unit box, of length \(O(\log{n})\), in contrast to the worst-case \(\Theta(\sqrt{n})\) bound, and
• a \(k\)-server solution of \(n\) requests from a unit interval, with total cost \(n^{O(1/\log k)}\), in contrast to the worst-case \(\Theta(n/k)\) bound.