Combinatorial Optimization
Fundamental combinatorial optimization problems spanning set systems, graph theory, and assignment. These problems form the backbone of theoretical computer science and have wide-ranging practical applications in scheduling, networking, and resource allocation.
View on GitHubProblem Collection
Eight fundamental problems in combinatorial optimization
Quick Navigation
Set Covering Problem
Given a universe U = {1,...,m} of elements and a collection of n weighted subsets, find a minimum-cost sub-collection covering all elements. The greedy algorithm achieves an H(m) ≤ ln(m)+1 approximation ratio, essentially best possible under standard complexity assumptions (Feige, 1998).
s.t. ∑{j: i ∈ Sj} xj ≥ 1 ∀ i ∈ U
xj ∈ {0, 1} ∀ j = 1,...,n
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| ILP Solver | Exact | NP-hard | MILP via SciPy (HiGHS solver) |
| Greedy Set Cover | Heuristic | O(m·n) | Chvátal (1979); ln(m)+1 approx |
Graph Coloring Problem
Assign colors to vertices of an undirected graph such that no two adjacent vertices share the same color, minimizing the number of colors used (chromatic number χ(G)). NP-hard to determine and inapproximable within n1−ε for any ε > 0 (Zuckerman, 2007).
s.t. ∑c=1..k xv,c = 1 ∀ v ∈ V (each vertex gets one color)
xu,c + xv,c ≤ 1 ∀ (u,v) ∈ E, ∀ c (adjacent vertices differ)
xv,c ≤ yc ∀ v, c (color c used only if opened)
xv,c, yc ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Sequential | Heuristic | O(V + E) | Welsh & Powell (1967) |
| Greedy Largest-First | Heuristic | O(V log V + E) | Static degree ordering, assign smallest color |
| DSatur | Heuristic | O(V²) | Brélaz (1979); dynamic saturation degree ordering |
Maximum Independent Set
Find the largest subset S of vertices such that no two vertices in S are adjacent. Equivalent to Maximum Clique on the complement graph &overline;G. NP-hard and inapproximable within n1−ε for any ε > 0.
s.t. xu + xv ≤ 1 ∀ (u,v) ∈ E (adjacent vertices cannot both be selected)
xv ∈ {0, 1} ∀ v ∈ V
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Branch and Bound | Exact | O(2n) | B&B with greedy upper bound pruning |
| Greedy Min-Degree | Heuristic | O(V + E) | Folklore; iteratively select minimum-degree vertex |
| Greedy Random | Heuristic | O(k·(V+E)) | Multi-start random vertex selection (k restarts) |
Minimum Vertex Cover
Find the smallest subset S of vertices such that every edge has at least one endpoint in S. NP-hard (Karp, 1972), but admits a simple 2-approximation via maximal matching. Complement of Maximum Independent Set: |MVC| = |V| − |MIS|.
s.t. xu + xv ≥ 1 ∀ (u,v) ∈ E (every edge covered)
xv ∈ {0, 1} ∀ v ∈ V
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Edge Cover | Heuristic | O(V + E) | 2-approx via maximal matching (folklore) |
| Greedy Degree Cover | Heuristic | O(V·E) | Iteratively select highest-degree vertex |
Maximum Clique
Find the largest complete subgraph (clique) in an undirected graph — a subset where every pair of vertices is connected. NP-hard and inapproximable within n1−ε for any ε > 0. Equivalent to MIS on the complement graph.
s.t. xu + xv ≤ 1 ∀ (u,v) ∉ E (non-adjacent vertices cannot both be selected)
xv ∈ {0, 1} ∀ v ∈ V
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Bron-Kerbosch | Exact | O(3n/3) | Bron & Kerbosch (1973); bound by Tomita et al. (2006) |
| Greedy Clique | Heuristic | O(V·E) | Greedy vertex addition by degree in subgraph |
Quadratic Assignment Problem
Given n facilities and n locations with flow matrix F and distance matrix D, find an assignment minimizing ∑ F[i,j] · D[π(i), π(j)]. Formulated by Koopmans & Beckmann (1957). One of the hardest combinatorial optimization problems — exact solutions are intractable beyond small instances. Generalizes the Linear Assignment Problem. Standard benchmark library: QAPLIB.
s.t. ∑k=1..n xik = 1 ∀ i (each facility to one location)
∑i=1..n xik = 1 ∀ k (each location to one facility)
xik ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Construction | Heuristic | O(n²) | Flow-distance interaction greedy |
| Simulated Annealing | O(iter·n) | Pairwise swap with Boltzmann acceptance |
Maximum Weight Set Packing
Given a universe of elements and a collection of weighted subsets, find a maximum-weight subcollection of pairwise disjoint sets. NP-hard; a simple greedy achieves a 1/k-approximation where k is the maximum set size. Dual of Set Covering in the set-system family.
s.t. ∑{j: i ∈ Sj} xj ≤ 1 ∀ i ∈ U (each element in at most one selected set)
xj ∈ {0, 1} ∀ j = 1,...,n
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Set Packing | Heuristic | O(n·m) | Folklore; weight-density greedy, 1/k-approx |
Job Sequencing with Deadlines
Given n unit-time jobs with profits wj and deadlines dj, select and sequence a subset on a single machine to maximize total profit of on-time jobs. Equivalently, minimize the weighted number of tardy jobs (ΣwjUj). The unit-weight case is solvable in O(n log n) by Moore's algorithm; the weighted case is NP-hard.
s.t. ∑{j: dj ≤ t} xj ≤ t ∀ t = 1,...,n (at most t jobs with deadline ≤ t)
xj ∈ {0, 1} ∀ j = 1,...,n
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Profit | Heuristic | O(n²) | Sort by profit, assign to latest available slot |
| Greedy EDD | Heuristic | O(n log n) | Earliest deadline first ordering |
Problem Relationships
Complement and duality connections across the combinatorial family
The Graph Trinity
Largest complete subgraph
Complement graph transform
Set complement
These three problems are fundamentally linked through graph complementation. A maximum clique in G is a maximum independent set in the complement graph &overline;G. A minimum vertex cover is the complement of a maximum independent set: |MVC| = |V| − |MIS|. Solving any one of these problems on a graph immediately solves the other two. All three share the same n1−ε inapproximability barrier.
Set System Duality
min cost: cover all elements
max weight: disjoint sets
Set Covering and Set Packing are LP duals in the set-system family. Covering asks: what is the cheapest sub-collection such that every element is covered at least once? Packing asks: what is the most valuable sub-collection such that no element appears more than once? The LP relaxation of one provides bounds for the other. This duality extends to Graph Coloring (partition vertices into independent sets — a set-cover-like structure) and Max Clique (find a maximum set packing in the edge complement).
● Polynomial — Vertex Cover has a 2-approximation via maximal matching. Set Covering has a ln(m)+1 greedy approximation. These are the "easiest" NP-hard problems here.
● Inapproximable — MIS, Max Clique, and Graph Coloring cannot be approximated within n1−ε for any ε > 0 (under standard assumptions). These are among the hardest problems to approximate in all of combinatorics.
● Notoriously Hard — QAP is one of the hardest structured optimization problems. Unlike graph problems, it has no known constant-factor approximation and remains challenging even for moderate sizes on the QAPLIB benchmark suite.
Algorithm Overview
Method distribution across the combinatorial family
| Problem | Exact | Heuristic | Metaheuristic |
|---|---|---|---|
| Set Covering | ILP | Greedy | — |
| Graph Coloring | — | Sequential Largest-First DSatur | — |
| QAP | — | Greedy | |
| Max Independent Set | B&B | Min-Degree Random | — |
| Vertex Cover | — | Edge Degree | — |
| Max Clique | Bron-Kerbosch | Greedy | — |
| Set Packing | — | Greedy | — |
| Job Sequencing | — | Profit EDD | — |
Try It Yourself
Interactive solvers for Graph Coloring and the MIS / Vertex Cover / Clique trinity
Graph Coloring
Graph Trinity — MIS / Vertex Cover / Max Clique
Solve all three complement-related problems on the same graph. Selected vertices are highlighted. Observe how |MVC| = |V| − |MIS| and how Max Clique on G equals MIS on &overline;G.