Given an acyclic digraph $G = (V,E)$ and a positive integer $k$, the problem of Maximum Coverage $k$-Antichains (resp. Chains) denoted as MA-$k$ (resp. MC-$k$) asks to find $k$ sets of pairwise unreachable vertices, known as antichains (resp. $k$ subsequences of paths, known as chains), maximizing the number $α_k$ (resp. $β_k$) of vertices covered by these antichains (resp. chains). While MC-$k$ was solved in almost optimal $|E|^{1+o(1)}$ time~[Kogan and Parter, ICALP'22], the fastest algorithms for MA-$k$ are a $(k|E|)^{1+o(1)}$-time solution and a $|E|^{1+o(1)}$-time $1/2$ approximation~[Kogan and Parter, ESA'24]. We obtain the following for MA-$k$: - An algorithm running in $|E|^{1+o(1)}$ time, and an algorithm running in parameterized near-linear $\tilde{O}(α_k |E|)$ time. Our algorithms are simple solutions exploiting a paths-based proof of the Greene-Kleitman theorems leveraged by the greedy algorithm for set cover as well as recent advances in fast algorithms for flows and shortest paths. - An approximation algorithm running in parameterized linear time $O(α_1^2|V| + (α_1+k)|E|)$ with approximation ratio of $(1-1/e) > 0.63 > 1/2$, beating the state-of-the-art $1/2$ approximation. Our solution uses greedy for antichains and a simple strategy to amortize the cost of computing consecutive maximum antichains. We complement these results with two examples (one for chains and one for antichains) showing that, for every $k \ge 2$, greedy misses the tight $1/e$ portion of the optimal coverage for chains, and a $1/4$ portion for antichains. We also show that greedy is a $Ω(\log{|V|})$ factor away from minimality when required to cover all vertices: previously unknown for sets of chains or antichains.

The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees (BSTs) that implies interesting consequences such as static optimality, static finger, and working set property on any access sequence X = (x_1,x_2,… ,x_m). However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(log n)-competitive ratio to the optimal BST where n is the number of keys. In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. For each of the following results, there is a group access tree whose group access bound 1) Is O(√{log n})-competitive to the optimal BST. 2) Achieves the k-finger bound with an additive term of O(m log k log log n) (randomized) when the reference tree is an almost complete binary tree. 3) Satisfies the unified bound with an additive term of O(m log log n). 4) Matches the unified bound with a time window k with an additive term of O(m log k log log n) (randomized). Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of the Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.

Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within O(1) factor of the offline optimal. However, despite having received a lot of attention in the past four decades, the question has remained elusive even for highly restricted input. In this paper, we prove new bounds on the cost of Greedy in the “pattern avoidance” regime. Our new results include: • The (preorder) traversal conjecture for Greedy holds up to a factor of O(2α(n)), improving upon the bound of 2α(n)O(1) in (Chalermsook et al., FOCS 2015) where α(n) is the inverse Ackermann function of n. This is the best known bound obtained by any online BSTs. • We settle the postorder traversal conjecture for Greedy. Previously this was shown for Splay trees only in certain special cases (Levy and Tarjan, WADS 2019). • The deque conjecture for Greedy holds up to a factor of O(α(n)), improving upon the bound 2O(α(n)) in (Chalermsook, et al., WADS 2015). This is arguably “one step away” from the bound O(α*(n)) for Splay trees (Pettie, SODA 2010). • The split conjecture holds for Greedy up to a factor of O(2α(n)). Previously the factor of O(α(n)) was shown for Splay trees only in a special case (Lucas, 1988). The input sequences in traversal and deque conjectures are perhaps “easiest” in the pattern-avoiding input classes and yet among the most notorious special cases of the dynamic optimality conjecture. Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. We believe that this simple method will find further applications in doing amortized analysis of data structures via extremal combinatorics. Finally, we show the applicability of this technique to handle a class of increasingly complex pattern-avoiding input sequences, called k-increasing sequences. As a bonus, we discover a new class of permutation matrices whose extremal bounds are polynomially bounded. This gives a partial progress on an open question by Jacob Fox (2013). * The full version of the paper can be accessed at https://arxiv.org/abs/2211.04112

The long-standing dynamic optimality conjecture postulates the existence of a dynamic binary search tree (BST) that is O(1)-competitive to all other dynamic BSTs. Despite attempts from many groups of researchers, we believe the conjecture is still far-fetched. One of the main reasons is the lack of the "right" potential functions for the problem: existing results that prove various consequences of dynamic optimality rely on very different potential function techniques, while proving dynamic optimality requires a single potential function that can be used to derive all these consequences. In this paper, we propose a new potential function, that we call extended (geometric) inversion. Inversion is arguably the most natural potential function principle that has been used in competitive analysis but has never been used in the context of BSTs. We use our potential function to derive new results, as well as streamlining/strengthening existing results. First, we show that a broad class of BST algorithms (including Greedy and Splay) are O(1)-competitive to Move-to-Root algorithm and therefore have simulation embedding property - a new BST property that was recently introduced and studied by Levy and Tarjan (SODA 2019). This result, besides substantially expanding the list of BST algorithms having this property, gives the first potential function proof of the simulation embedding property for BSTs (thus unifying apparently different kinds of results). Moreover, our analysis is the first where the costs of two dynamic binary search trees are compared against each other directly and systematically. Secondly, we use our new potential function to unify and strengthen known BST bounds, e.g., showing that Greedy satisfies the weighted dynamic finger property within a multiplicative factor of (5+o(1)).