# combinatorial algorithms

The Design of Approximation Algorithms

Algorithms by Jeff Erickson

• covers historical context

Algorithms for Competitive Programming

bipartite b-matching

proof number search

Optimizing Joins

convex optimization

Fast Fourier Transform

In-place merging

Network Flow

single source shortest path

Shortest Common Supersequence

Perfect graphs

Level Set Tree

Interval Packing

Graph algorithms

Dynamic Programming

Complexity of integer division

Big Oh

dominating set

Algorithm Analysis

rank aggregation

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

discrete resource allocation

Combinatorial problems in genomics and computational biology

combinatorial games

Gene Team Tree

earth mover’s distance in 2D grid

succinct representations

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

# 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