ADVANCED ALGORITHMS - NP-COMPLETENESS:Approximation Algorithms for NP-Hard Problems

def vertex_cover_2_approx(graph):
    """
    2-approximation for minimum vertex cover.
    
    Algorithm: Greedily pick edges and take both endpoints.
    
    Correctness: Every optimal cover must include at least one endpoint
    of each selected edge. Since no two selected edges share an endpoint,
    optimal cover size ≥ (number of selected edges).
    Our cover size = 2 × (number of selected edges) ≤ 2 × OPT.
    """
    cover = set()
    matched = set()
    
    for u, v in graph.edges():
        if u not in matched and v not in matched:
            cover.add(u)
            cover.add(v)
            matched.add(u)
            matched.add(v)
    
    return cover

def set_cover_greedy(universe, sets):
    """
    Greedy log(n)-approximation for minimum set cover.
    
    At each step, pick the set covering the most uncovered elements.
    
    Proof: Let k = OPT. After t steps, at most n(1 - 1/k)^t elements
    remain uncovered. After k * ln(n) steps, < 1 element remains.
    So greedy uses ≤ k * ln(n) + 1 = O(OPT * log n) sets.
    """
    uncovered = set(universe)
    cover_indices = []
    
    while uncovered:
        # Find the set covering the most uncovered elements
        best_idx = max(range(len(sets)), 
                       key=lambda i: len(sets[i] & uncovered))
        cover_indices.append(best_idx)
        uncovered -= sets[best_idx]
    
    return cover_indices

def knapsack_fptas(weights, values, capacity, epsilon):
    """
    FPTAS for 0/1 Knapsack via value scaling.
    
    Scale values down by K = epsilon * max_value / n
    Solve exactly with scaled values (now fit in polynomial range)
    Return solution — at most (1 + epsilon) * OPT by scaling argument
    
    Time: O(n^2 / epsilon)
    """
    n = len(values)
    max_val = max(values)
    K = epsilon * max_val / n  # Scaling factor
    
    # Scale values
    scaled_values = [int(v / K) for v in values]
    max_scaled = sum(scaled_values)
    
    # DP on scaled values
    # dp[v] = minimum weight to achieve value v
    INF = float('inf')
    dp = [INF] * (max_scaled + 1)
    dp[0] = 0
    
    for i in range(n):
        new_dp = dp[:]
        for v in range(scaled_values[i], max_scaled + 1):
            if dp[v - scaled_values[i]] + weights[i] <= capacity:
                new_dp[v] = min(new_dp[v], dp[v - scaled_values[i]] + weights[i])
        dp = new_dp
    
    # Find maximum achievable value
    best_val = 0
    for v in range(max_scaled, -1, -1):
        if dp[v] <= capacity:
            best_val = v * K  # Un-scale
            break
    
    return best_val