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 orO(n^2)time using only equality comparisons