Belajar Algoritm - Approximation & Online Algorithms

#Pendahuluan

Setelah di episode 24 kita membahas Randomized Algorithms, pada episode ini kita membahas Approximation & Online Algorithms — dua kategori yang relevan ketika solusi optimal tidak praktis (terlalu lambat) atau tidak mungkin (informasi tidak lengkap).

Approximation algorithms menawarkan solusi hampir optimal dengan jaminan kualitas — kita tahu seberapa jauh solusi dari optimal. Online algorithms membuat keputusan tanpa knowledge masa depan — dan kita ingin menjamin kualitas keputusan dibandingkan situasi ideal jika semua informasi tersedia.

#Approximation Algorithms

Approximation ratio: rasio antara solusi approximation dan solusi optimal. Jika solusi optimal = OPT, approximation ratio α berarti solusi approximation ≤ α × OPT (untuk minimization) atau ≥ OPT/α (untuk maximization).

#Vertex Cover 2-Approximation

Vertex cover: pilih minimum vertex sehingga setiap edge minimal memiliki satu endpoint yang dipilih. NP-hard untuk minimum vertex cover.

2-approximation: pilih semua edge, untuk setiap edge yang belum ter-cover, pilih kedua endpoint-nya. Solusi ≤ 2 × OPT.

def approx_vertex_cover(edges, n):
    """edges: list of (u, v)"""
    covered = set()
    selected = set()
    remaining = set(range(n))
    
    for u, v in edges:
        if u not in covered or v not in covered:
            selected.add(u)
            selected.add(v)
            covered.add(u)
            covered.add(v)
    
    return selected

Mengapa 2-approx?: setiap edge yang dipilih minimal memiliki satu endpoint di optimal solution. Kita memilih dua endpoint per edge → ≤ 2 × |OPT|.

#Set Cover (ln n)-Approximation

Set cover: pilih minimum jumlah set sehingga union-nya mencakup semua elemen. NP-hard, tetapi greedy memberikan approximation ratio O(ln n).

def approx_set_cover(universe, sets):
    """Greedy set cover: O(ln n) approximation"""
    uncovered = set(universe)
    selected = []
    
    while uncovered:
        # Pilih set yang mencakup paling banyak uncovered elements
        best_set = max(sets, key=lambda s: len(s & uncovered))
        if not (best_set & uncovered):
            break
        selected.append(best_set)
        uncovered -= best_set
    
    return selected

Bukti O(ln n): setiap iterasi menutupi setidaknya 1/|uncovered| dari elemen yang tersisa → O(ln n) iterasi.

#Kapan Approximation Cukup?

#Online Algorithms

Online algorithm: membuat keputusan input per input tanpa melihat input masa depan. Competitive ratio: rasio antara performa online dan performa optimal offline (yang tahu semua input sebelumnya).

#Ski Rental Problem

Masalah klasik: kalian bisa sewa ski ($1/hari) atau beli ski ($B). Berapa hari kalian harus menyewa sebelum memutuskan beli?

Strategi optimal: sewa selama B-1 hari, beli di hari ke-B.

• Jika liburan ≤ B-1 hari: optimal (hanya sewa).
• Jika liburan ≥ B hari: spend 2B-1 = O(B) dibanding optimal B → competitive ratio 2.

def ski_rental(decision_point, buy_threshold, cost_rent, cost_buy):
    """Simulasi ski rental"""
    total = 0
    for day in range(1, decision_point + 1):
        if day < buy_threshold:
            total += cost_rent
        else:
            total += cost_buy
            break
    return total

#Competitive Ratio

#Praktik

Implementasi greedy approximation untuk Travelling Salesman Problem (nearest neighbor heuristic) pada graph kecil (5-10 kota). Bandingkan hasil dengan optimal (brute force). Hitung approximation ratio aktual.

#Penutup

Pada episode 25 ini, kalian telah memahami:

• Approximation algorithms: solusi hampir optimal dengan jaminan kualitas.
• Vertex cover 2-approx: sederhana, jaminan ≤ 2× optimal.
• Set cover O(ln n)-approx: greedy, jaminan O(ln n)× optimal.
• Online algorithms: decision tanpa future knowledge, diukur dengan competitive ratio.
• Ski rental: competitive ratio 2 — strategi sederhana yang optimal.

Di episode 26 selanjutnya kita akan membahas Problem Classification, Tren 2026 & Competitive Programming Patterns — pola masalah, tren AI algorithms, dan pattern recognition untuk coding interview. Sampai jumpa di episode 26!