Average-case hardness measures how difficult a problem is on the instances encountered in practical scenarios, rather than on its hardest possible inputs. This distinction explains why heuristics can be useful even when worst-case guarantees are discouraging. section 16.1.1
Use the concept to guide algorithm choices:
- Accept a suboptimal answer when obtaining a useful result quickly matters more than guaranteeing the optimum. section 16.1.1
- Distinguish rare hard edge cases from the typical inputs produced by real applications. section 16.1.1
- Prefer heuristics with proven accuracy bounds when available. section 16.1.1
Graph embedding
Randomly assign graph vertices to positions, reject invalid embeddings, count edge intersections, and retain the valid arrangement with the fewest crossings. Repeated sampling may work well in practice without guaranteeing the optimum. section 16.1.1
