Multi-Dimensional Matching Algorithm

Matching Optimization Problem

Maximize: Σᵢ Σⱼ φ(tᵢ, wⱼ) · xᵢⱼ

Constraints:
1. Σⱼ xᵢⱼ ≤ 1 (Each task to at most one worker)
2. Σᵢ xᵢⱼ ≤ Cⱼ (Worker capacity constraint)
3. d(tᵢ, wⱼ) ≤ D_max (Geographic distance constraint)
4. skills(tᵢ) ⊆ skills(wⱼ) (Skill matching constraint)
5. R_j ≥ R_min(tᵢ) (Reputation lower bound constraint)
6. time_conflict(tᵢ, tₖ) → xᵢⱼ + xₖⱼ ≤ 1 (Time conflict constraint)

Where xᵢⱼ ∈ {0,1}

Heuristic Solution Algorithm

Since this problem is NP-Hard, we employ a variant of the Gale-Shapley stable matching algorithm [4]:

def stable_matching(tasks, workers):
    """
    Stable matching algorithm
    Time complexity: O(n·m·log(m))
    Space complexity: O(n·m)
    """
    # 1. Compute utility for all feasible pairs
    utility_matrix = compute_utility(tasks, workers)
    
    # 2. Tasks rank workers by preference
    task_preferences = sort_by_utility(tasks, utility_matrix)
    
    # 3. Iterative matching
    unmatched_tasks = set(tasks)
    matches = {}
    
    while unmatched_tasks:
        task = unmatched_tasks.pop()
        worker = task_preferences[task][0]
        
        if worker.is_available():
            matches[task] = worker
            worker.assign(task)
        else:
            # Check for better match
            current_task = worker.current_task
            if utility(task, worker) > utility(current_task, worker):
                unmatched_tasks.add(current_task)
                matches[task] = worker
                worker.reassign(task)
                del matches[current_task]
            else:
                task_preferences[task].remove(worker)
                unmatched_tasks.add(task)
    
    return matches

Performance Analysis:

• Worst-case time complexity: O(n²)

• Average-case time complexity: O(n·log(n))

• Guarantees stable matching (no blocking pair)