ADVANCED ALGORITHMS - ADVANCED TECHNIQUES:Approximation Algorithms — Practical NP-hard Solutions

def vertex_cover_approx(graph):
    """2-approximation for Vertex Cover via maximal matching."""
    cover = set()
    edges_covered = set()
    
    for u in graph:
        for v in graph[u]:
            edge = (min(u,v), max(u,v))
            if edge not in edges_covered and u not in cover and v not in cover:
                cover.add(u)
                cover.add(v)
                # Mark all edges incident to u and v as covered
                for neighbor in graph[u]:
                    edges_covered.add((min(u, neighbor), max(u, neighbor)))
                for neighbor in graph[v]:
                    edges_covered.add((min(v, neighbor), max(v, neighbor)))
    
    return cover

# Example
graph = {0: [1,2], 1: [0,2,3], 2: [0,1,4], 3: [1,4], 4: [2,3]}
print(vertex_cover_approx(graph))  # Some 2-approximation

import heapq

def metric_tsp_approx(dist):
    """2-approximation for metric TSP using MST DFS tour."""
    n = len(dist)
    
    # Step 1: Prim's MST
    in_mst = [False] * n
    min_edge = [float('inf')] * n
    parent = [-1] * n
    min_edge[0] = 0
    heap = [(0, 0)]
    mst_adj = {i: [] for i in range(n)}
    
    while heap:
        cost, u = heapq.heappop(heap)
        if in_mst[u]: continue
        in_mst[u] = True
        if parent[u] != -1:
            mst_adj[parent[u]].append(u)
            mst_adj[u].append(parent[u])
        for v in range(n):
            if not in_mst[v] and dist[u][v] < min_edge[v]:
                min_edge[v] = dist[u][v]
                parent[v] = u
                heapq.heappush(heap, (dist[u][v], v))
    
    # Step 2: DFS pre-order traversal
    visited = [False] * n
    tour = []
    
    def dfs(node):
        visited[node] = True
        tour.append(node)
        for neighbor in mst_adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)
    
    dfs(0)
    tour.append(0)  # Return to start
    
    # Calculate tour cost
    cost = sum(dist[tour[i]][tour[i+1]] for i in range(len(tour)-1))
    return tour, cost

def set_cover_greedy(universe, subsets):
    """Greedy set cover — O(log n) approximation."""
    covered = set()
    chosen = []
    remaining_subsets = [set(s) for s in subsets]
    
    while covered != universe:
        # Pick subset with maximum new coverage
        best_idx = max(range(len(remaining_subsets)),
                      key=lambda i: len(remaining_subsets[i] - covered))
        best = remaining_subsets[best_idx]
        
        if not (best - covered):
            break  # No progress possible
        
        covered |= best
        chosen.append(subsets[best_idx])
    
    return chosen

universe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
subsets = [{1,2,3,8},{1,2,3,4,5},{4,5,7},{5,6,7},{6,7,8,9,10}]
print(set_cover_greedy(universe, subsets))

def knapsack_fptas(weights, values, capacity, epsilon):
    """(1+epsilon)-approximation for 0/1 Knapsack."""
    n = len(values)
    if n == 0: return 0
    
    V_max = max(values)
    # Scale factor: we'll round values down to multiples of K
    K = epsilon * V_max / n
    
    if K == 0:  # epsilon = 0, exact solution needed
        K = 1
    
    # Scale values (round down)
    scaled_values = [int(v / K) for v in values]
    max_scaled = sum(scaled_values)
    
    # DP on scaled values: dp[v] = min weight to achieve scaled value v
    dp = [float('inf')] * (max_scaled + 1)
    dp[0] = 0
    
    for i in range(n):
        for v in range(max_scaled, scaled_values[i] - 1, -1):
            if dp[v - scaled_values[i]] + weights[i] <= capacity:
                dp[v] = min(dp[v], dp[v - scaled_values[i]] + weights[i])
    
    # Find maximum achievable scaled value within capacity
    best_scaled = max(v for v in range(max_scaled + 1) if dp[v] <= capacity)
    
    # Convert back using original values approximation
    return best_scaled * K

# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 7]
capacity = 7
print(f"FPTAS result: {knapsack_fptas(weights, values, capacity, 0.1):.2f}")