Algorithm Decision Guide

Algorithm Decision Guide

Use this flowchart to select the appropriate matching algorithm. Answer each question in order.

Decision Flowchart

START
  │
  ▼
┌─────────────────────────────────────┐
│ Q1: Do BOTH sides have preferences? │
└─────────────────────────────────────┘
  │
  ├─► YES ──► Q2 (Two-Sided)
  │
  └─► NO ───► Q5 (One-Sided)


TWO-SIDED PATH
══════════════

┌────────────────────────────────────────┐
│ Q2: Is STABILITY required?             │
│ (No pair should prefer each other      │
│  over their assigned matches)          │
└────────────────────────────────────────┘
  │
  ├─► YES ──► Q3 (Stable Matching)
  │
  └─► NO ───► Q4 (Optimization)

┌────────────────────────────────────────┐
│ Q3: One-to-one or many-to-one?         │
└────────────────────────────────────────┘
  │
  ├─► ONE-TO-ONE ──► GALE-SHAPLEY
  │
  └─► MANY-TO-ONE ─► HOSPITAL-RESIDENT (Gale-Shapley variant)

┌────────────────────────────────────────┐
│ Q4: Do matches have weights/costs?     │
└────────────────────────────────────────┘
  │
  ├─► YES ──► Q6 (Weighted)
  │
  └─► NO ───► HOPCROFT-KARP (maximum cardinality)


ONE-SIDED PATH
══════════════

┌────────────────────────────────────────┐
│ Q5: Can ANY entity match ANY other?    │
│ (Non-bipartite graph)                  │
└────────────────────────────────────────┘
  │
  ├─► YES ──► BLOSSOM ALGORITHM
  │
  └─► NO ───► Q4 (Optimization)


WEIGHTED PATH
═════════════

┌────────────────────────────────────────┐
│ Q6: Is the preference graph sparse?    │
│ (Each entity prefers << n others)      │
└────────────────────────────────────────┘
  │
  ├─► YES (sparse) ──► AUCTION ALGORITHM
  │
  └─► NO (dense) ────► HUNGARIAN ALGORITHM


HIERARCHY PATH (applies to any above)
═════════════════════════════════════

┌────────────────────────────────────────┐
│ Q7: Is matching hierarchical/nested?   │
└────────────────────────────────────────┘
  │
  ├─► YES ──► Q8
  │
  └─► NO ───► Use algorithm from above directly

┌────────────────────────────────────────┐
│ Q8: Do parent decisions constrain      │
│     children, or do children inform    │
│     parent decisions?                  │
└────────────────────────────────────────┘
  │
  ├─► PARENT CONSTRAINS CHILDREN ──► TOP-DOWN + chosen algorithm per level
  │
  └─► CHILDREN INFORM PARENT ──────► BOTTOM-UP aggregation + match at root


ENTITY RESOLUTION PATH
══════════════════════

┌────────────────────────────────────────┐
│ Q9: Is this fuzzy/probabilistic        │
│     matching (entity resolution)?      │
└────────────────────────────────────────┘
  │
  ├─► YES ──► BLOCKING + SCORING pipeline
  │           (optionally Fellegi-Sunter for probabilistic)
  │
  └─► NO ───► Use decision tree above

Quick Reference Table

Constraint Compatibility Matrix

Check that your constraints are compatible with the chosen algorithm:

¹ Can force by truncating preference lists, but may cause instability ² Requires creating composite entities or post-processing

Decision Examples

Example 1: School Choice

Students rank schools, schools have capacities, want stable assignment

• Q1: Both sides have preferences? YES
• Q2: Stability required? YES (no student-school pair should want to deviate)
• Q3: One-to-one or many-to-one? MANY-TO-ONE (schools take multiple students)

→ HOSPITAL-RESIDENT (student-proposing Gale-Shapley)

Example 2: Task Assignment

Assign tasks to workers to minimize total cost, workers have capacity

• Q1: Both sides have preferences? NO (tasks don't prefer workers)
• Q5: Non-bipartite? NO (workers and tasks are distinct sets)
• Q4: Weighted? YES (minimizing cost)
• Q6: Sparse? NO (any worker can do any task)

→ HUNGARIAN ALGORITHM (expand workers to capacity)

Example 3: Org Restructuring

Match employees to new positions across department hierarchy

• Q7: Hierarchical? YES (org → dept → team → position)
• Q8: Direction? PARENT CONSTRAINS (dept capacity limits teams)
• Q1: Both sides have preferences? YES (employees rank positions, managers rank employees)
• Q2: Stability required? YES

→ TOP-DOWN hierarchical Gale-Shapley

Example 4: Customer Deduplication

Identify same customer across databases with fuzzy name/address matching

• Q9: Entity resolution? YES

→ BLOCKING (by zip + name prefix) + SCORING (Jaro-Winkler on names) + threshold clustering

Red Flags: Wrong Algorithm Indicators

Algorithm Selection Checklist

Before finalizing choice:

□ Algorithm handles all HARD constraints
□ Algorithm complexity acceptable for data size
□ Stability vs optimality tradeoff understood
□ Hierarchy traversal direction determined (if applicable)
□ Tie-breaking strategy compatible with algorithm
□ Edge cases documented (what happens with empty/single/tied?)