Heuristics — Characteristics & Application Domains

What is a Heuristic?

Problem-solving technique using practical, rule-of-thumb, or educated-guess approach that is not guaranteed optimal but gives good enough quickly for hard (often NP-hard) problems. Heuristics trade optimality for speed/feasibility.

Characteristics

• No guarantee of optimal or bounded approximation (vs approximation algorithm has ratio bound; heuristic may be unbounded).
• Problem-specific knowledge embedded (e.g., nearest neighbor for TSP).
• Fast, simple — polytime, often $O(n\log n)$ or $O(n^2)$, usable where exact exponential infeasible.
• Empirically good — works well on typical instances despite worst pathological cases.
• No need to prove ratio — evaluated by experiments/benchmarks.
• Can be combined with metaheuristics (simulated annealing, genetic algorithms, tabu search) for improvement.

vs Approximation Algorithms

Heuristic	Approximation Algorithm
No proven bound	Proven ratio $ρ$ guarantee
Often faster/simpler	May be more complex (LP rounding)
Used when bound not needed	Used when guarantee required

Application Domains

• Combinatorial Optimization: TSP (nearest neighbor, 2-opt), Knapsack (greedy ratio), Bin Packing (FF/BF), Graph Coloring (greedy ordering), Vertex Cover (max degree greedy), Scheduling (list scheduling LPT).
• AI Search: A* heuristic $h(n)$ (admissible Manhattan distance for 8-puzzle, Euclidean for pathfinding) — guides search.
• Routing & Networks: Vehicle routing, network design.
• Resource Allocation: Task scheduling, load balancing, memory allocation.
• Machine Learning: Feature selection heuristics, decision tree splits (information gain).

Examples: Bin Packing First Fit, TSP nearest neighbor tour, Sudoku backtracking with MRV heuristic.