Key Concepts in Combinatorial Optimization Problems

Why This Matters

Combinatorial optimization sits at the heart of computer science and discrete mathematics—it's where theoretical elegance meets real-world problem solving. You're being tested on your ability to recognize problem structures, understand computational complexity, and select appropriate algorithmic strategies. These problems appear everywhere: from routing delivery trucks to scheduling exams to designing computer chips. The key insight is that while many of these problems are NP-hard (meaning no efficient exact solution exists for large inputs), understanding their structure helps you choose the right approximation algorithms, heuristics, or special-case solutions.

Don't just memorize problem names and their definitions. Know why certain problems are computationally hard, how different problems relate to each other, and which algorithmic techniques apply to each category. Exam questions often ask you to identify which optimization framework fits a given scenario, compare the complexity of related problems, or explain why a greedy approach works for one problem but fails for another.

---

Path and Flow Optimization

These problems focus on finding optimal routes or maximizing throughput through network structures. The underlying principle is that graphs model connectivity, and edge weights capture costs or capacities.

Traveling Salesman Problem

• NP-hard complexity—no known polynomial-time algorithm exists, making it a benchmark for computational hardness
• Hamiltonian cycle with minimum total weight; must visit every vertex exactly once and return to start
• Heuristics dominate in practice; nearest neighbor, 2-opt, and genetic algorithms provide near-optimal solutions for logistics and circuit design

Shortest Path Problem

• Dijkstra's algorithm runs in $O((V + E) \log V)$ for graphs with non-negative edge weights
• Bellman-Ford handles negative weights in $O(VE)$ time and detects negative cycles
• Foundation for navigation—GPS systems, network routing protocols, and urban planning all depend on efficient shortest path computation

Maximum Flow Problem

• Ford-Fulkerson method iteratively finds augmenting paths until no more exist; Edmonds-Karp guarantees $O(VE^2)$ using BFS
• Capacity constraints limit flow on each edge; flow conservation requires inflow equals outflow at every non-terminal vertex
• Max-flow min-cut theorem—the maximum flow equals the minimum cut capacity, connecting flow problems to graph partitioning

---

Packing and Covering Problems

These problems involve selecting subsets to either fill a container optimally (packing) or ensure complete coverage (covering). The tension between these dual perspectives is a recurring exam theme.

Knapsack Problem

• 0/1 version uses dynamic programming in $O(nW)$ pseudo-polynomial time; fractional version yields to greedy selection by value-to-weight ratio
• Capacity constraint $\sum w_i x_i \leq W$ with objective to maximize $\sum v_i x_i$
• Resource allocation archetype—budgeting, investment portfolios, and cargo loading all follow this structure

Bin Packing Problem

• NP-hard with no polynomial-time exact solution; First Fit Decreasing heuristic guarantees at most $\frac{11}{9} \cdot OPT + \frac{6}{9}$ bins
• Fixed bin capacity distinguishes this from knapsack; goal is minimizing number of bins, not maximizing value
• Practical applications include server load balancing, cutting stock problems, and container shipping logistics

Set Cover Problem

• Greedy algorithm achieves $O(\ln n)$ approximation ratio—provably the best possible unless $P = NP$
• Input structure: universe $U$, collection of subsets $S_1, S_2, \ldots, S_m$; goal is minimum subsets covering all of $U$
• Generalizes vertex cover—understanding this relationship helps you recognize equivalent problem formulations on exams

---

Graph Structure Problems

These problems extract or exploit structural properties of graphs—connectivity, independence, and partitioning. Understanding graph structure often reveals efficient algorithms or proves hardness.

Minimum Spanning Tree

• Prim's algorithm grows one tree from a starting vertex in $O(E \log V)$; Kruskal's builds a forest by sorting edges
• Greedy works perfectly here—both algorithms find the globally optimal solution, unlike most NP-hard problems
• Network design foundation—telecommunications, power grids, and transportation networks minimize infrastructure cost using MST

Vertex Cover

• NP-hard but admits a simple 2-approximation: repeatedly pick both endpoints of any edge
• Minimum set of vertices such that every edge has at least one endpoint in the set
• Dual to independent set—if $S$ is a vertex cover, then $V - S$ is an independent set, linking these classic problems

Graph Coloring

• Chromatic number $\chi(G)$ is the minimum colors needed; computing it is NP-hard for general graphs
• Adjacent vertices must receive different colors; planar graphs always satisfy $\chi(G) \leq 4$ (Four Color Theorem)
• Scheduling applications—exam scheduling, register allocation in compilers, and frequency assignment all reduce to graph coloring

---

Assignment and Matching Problems

These problems pair elements from two sets optimally. The key structure is the bipartite graph, where edges connect elements across sets but never within the same set.

Assignment Problem

• Hungarian algorithm solves in $O(n^3)$ time—polynomial complexity makes this tractable unlike most optimization problems
• Bipartite matching with costs; each agent assigned exactly one task, minimizing total cost or maximizing total profit
• Linear programming relaxation naturally produces integer solutions due to the total unimodularity of the constraint matrix

---

Quick Reference Table

---

Self-Check Questions

1. Which two problems are both NP-hard but have fundamentally different approximation guarantees—one admitting a constant-factor approximation and one only a logarithmic approximation? Explain why.

2. Compare and contrast the Knapsack Problem and Bin Packing Problem: what structural difference explains why dynamic programming solves one efficiently but not the other?

3. Both Minimum Spanning Tree and Shortest Path operate on weighted graphs. Why does the greedy approach guarantee optimality for MST but require more careful algorithm design (like Dijkstra's) for shortest paths?

4. If an FRQ describes a scenario where you must assign $n$ workers to $n$ jobs with varying efficiency ratings, which problem framework applies, and what algorithm would you recommend?

5. Vertex Cover and Independent Set are called "dual" problems. If a graph has 10 vertices and a minimum vertex cover of size 4, what is the size of its maximum independent set, and why?