# combinatorial algorithms

The Design of Approximation Algorithms

- covers historical context

Algorithms for Competitive Programming

Complexity of integer division

Distribute cards into 13 piles. They can always be arranged with distinct ranks as the first card.

- application of Hall’s Theorem
- reference: https://www.jstor.org/stable/2589146

Combinatorial problems in genomics and computational biology

earth mover’s distance in 2D grid

Exact TSP solver

smallest automata to separate two words

Optimal Algorithm Configuration

scheduling elevators

online graph exploration

- used by robot vacuum cleaner to clean every location
- start from s visit all nodes and return to s, minimize the total cost
- DFS has competitive ratio 2 for unweighted undirected graph and that is optimal

finding code clones with mismatches

# Graph isomorphism

Babai 2017, \(2^{O(\log^3 n)}\)

Babai and Luks 1983, \(2^{O(\sqrt{n \log n})}\)

# Group isomorphism

Xiaorui Sun 2023, \(n^{O(\log^{5/6} n)}\) for p-groups of class 2 and exponent p for prime p > 2.

Tarjan 1978, \(n^{\log n + O(1)}\)

# Techniques/tricks

- Tournament
- Naming technique
- A Combinatorial Approach to Automatic Discovery of Cluster-Patterns, WABI 2003

- Decreasing the level of granularity
- start with large step length, half in each step, eg. n/2,…,8,4,2,1
- Jump Flooding Algorithm
- compute approximate vornoroi diagram quickly on GPU

- Lazy
- avoid doing work unless absolutely necessary

- Relax the condition
- Weaker structural property allows structures to be maintained more easily
- Eg. Melding of leftist heaps, AVL property and balance

# Data structures

- Suffix tree
- PQ tree
- Threaded binary tree
- Optimal resizable arrays
- extension of Resizable Arrays in Optimal Time and Space

# Order statistics

- selection can be solved in linear time
- majority can be found in linear time
- mode can be found in
`O(nlgn)`

time with a total ordering or`O(n^2)`

time using only equality comparisons