Approximation Algorithms

Masalah NP-hard seperti vertex cover, traveling salesman, dan set cover tidak memiliki algoritma polinomial (kecuali P = NP). Untuk input besar, algoritma eksak (backtracking, branch-and-bound) menjadi tidak praktis. Approximation algorithm adalah jalan tengah: jalankan algoritma polinomial yang memberi solusi terjamin dekat dengan optimal. Kuncinya adalah approximation ratio — jaminan formal bahwa solusi berada dalam faktor tertentu dari optimal. Pada Chapter ini kita membedah tiga algoritma klasik: vertex cover 2-approximation, TSP metric 2-approximation via MST, dan greedy set cover dengan ratio O(ln n). Semua diimplementasikan dalam C++ yang dapat diuji.

Aturan: Approximation Ratio #

Sebuah algoritma memiliki approximation ratio α untuk minimization problem bila:

cost(ALG(x)) ≤ α · cost(OPT(x))   untuk semua input x

di mana ALG(x) adalah solusi algoritma dan OPT(x) adalah solusi optimal. Untuk maximization problem: cost(ALG(x)) ≥ (1/α) · cost(OPT(x)).

Ratio 1 berarti algoritma selalu menemukan solusi optimal (exact). Ratio 2 berarti solusi paling buruk dua kali lipat optimal.

Vertex Cover 2-Approximation #

Mekanisme: Greedy Edge-Pick #

1. Selama masih ada edge yang belum ter-cover:
   • Ambil edge (u, v) apa pun.
   • Tambahkan kedua u dan v ke vertex cover.
   • Tandai semua edge incident ke u atau v sebagai ter-cover.
2. Berhenti saat semua edge ter-cover.

Analisis rasio: Misalkan algoritma memilih k edge yang “bebas” (kedua endpoint belum di-cover). Setiap pasangan (u, v) yang dipilih menambah 2 vertex ke cover. Optimal harus menutup setiap edge yang dipilih — karena edge-edge ini tidak share vertex (keduanya baru), optimal harus memilih ≥ 1 vertex per edge tersebut. Jadi |OPT| ≥ k dan |ALG| = 2k, sehingga |ALG| / |OPT| ≤ 2.

Kode: Vertex Cover 2-Approximation #

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

// Vertex Cover 2-approximation
// Input: graph sebagai daftar edge (u, v).
// Output: vector vertex yang dipilih sebagai cover.
vector<int> vertex_cover_2approx(int n, const vector<pair<int,int>>& edges) {
    vector<bool> in_cover(n, false);
    vector<int> result;
    for (auto [u, v] : edges) {
        if (in_cover[u] || in_cover[v]) continue;  // edge sudah tercover
        in_cover[u] = true;
        in_cover[v] = true;
        result.push_back(u);
        result.push_back(v);
    }
    return result;
}

int main() {
    // Graph: 4-cycle 0-1-2-3-0
    int n = 4;
    vector<pair<int,int>> edges = {{0,1}, {1,2}, {2,3}, {3,0}};

    auto cover = vertex_cover_2approx(n, edges);
    cout << "Graph: 4-cycle (4 node, 4 edge)\n";
    cout << "Vertex cover (2-approx): { ";
    for (int v : cover) cout << v << ' ';
    cout << "} (size " << cover.size() << ")\n";
    cout << "Optimal: { 0 2 } atau { 1 3 } (size 2)\n";
    cout << "Rasio: " << (double)cover.size() / 2.0 << '\n';
    return 0;
}

Output yang Dihasilkan:

Graph: 4-cycle (4 node, 4 edge)
Vertex cover (2-approx): { 0 1 2 3 } (size 4)
Optimal: { 0 2 } atau { 1 3 } (size 2)
Rasio: 2

Bedah Kode Baris-per-Baris #

1. vector<bool> in_cover(n, false): tracking vertex mana yang sudah dipilih. vector<bool> hemat memori (1 bit per elemen), tetapi sedikit lebih lambat dari vector<char> karena bit-packing. Untuk demo kecil, perbedaan tidak signifikan.
2. for (auto [u, v] : edges): iterasi edge sesuai urutan input. Hasil bisa berbeda tergantung urutan — semua valid sebagai 2-approximation.
3. if (in_cover[u] || in_cover[v]) continue: lewati edge yang sudah ter-cover (salah satu endpoint sudah dipilih di iterasi sebelumnya). Ini inti algoritma.
4. in_cover[u] = in_cover[v] = true; result.push_back(u); result.push_back(v): tambahkan kedua endpoint ke cover. Inilah sumber rasio 2: algoritma “over-cover” dengan memilih dua vertex padahal optimal cukup satu.
5. Verifikasi: 4-cycle, algoritma memilih (0,1) → add 0, 1; lalu (1,2) → skip (1 sudah di-cover); lalu (2,3) → add 2, 3; lalu (3,0) → skip. Total 4 vertex. Optimal = 2 vertex ({0,2} atau {1,3}). Rasio = 4/2 = 2.0 — mencapai worst case.

TSP Metric 2-Approximation #

Mekanisme: MST + Preorder Walk #

Untuk metric TSP (jarak memenuhi triangle inequality: d(a,c) ≤ d(a,b) + d(b,c)):

1. Bangun Minimum Spanning Tree (MST) dari graph. Cost MST ≤ OPT karena menghapus satu edge dari tur optimal memberi spanning tree.
2. Lakukan preorder DFS walk dari sembarang node — kunjungi setiap node sekali, mencatat urutan.
3. Hubungkan kembali ke titik awal untuk menutup tur.

Analisis rasio: DFS walk pada MST menelusuri setiap edge MST tepat dua kali (pergi dan pulang). Total walk cost = 2 · MST. Karena tur preorder skip node yang sudah dikunjungi (langsung lompat ke node berikutnya), triangle inequality memastikan jarak lompatan ≤ jarak walk yang di-skip. Jadi:

cost(ALG) ≤ 2 · MST ≤ 2 · OPT

Rasio = 2.

Kode: TSP 2-Approximation #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class TSP2Approx {
    int n;
    vector<vector<pair<int,int>>> adj;
    vector<bool> visited;
    vector<int> tour;

    void dfs(int u) {
        visited[u] = true;
        tour.push_back(u);
        for (auto [v, w] : adj[u]) {
            if (!visited[v]) dfs(v);
        }
    }
public:
    TSP2Approx(int n) : n(n), adj(n), visited(n, false) {}

    void add_mst_edge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int compute_tour(int start, const vector<vector<int>>& dist) {
        dfs(start);
        int total = 0;
        for (int i = 0; i + 1 < (int)tour.size(); ++i) {
            total += dist[tour[i]][tour[i+1]];
        }
        total += dist[tour.back()][tour[0]];  // tutup tur
        return total;
    }

    void print_tour() const {
        for (int i = 0; i < (int)tour.size(); ++i) {
            cout << tour[i];
            if (i + 1 < (int)tour.size()) cout << " -> ";
        }
        cout << " -> " << tour[0] << '\n';
    }
};

int main() {
    // 5 kota dengan matriks jarak (simetris, memenuhi triangle inequality)
    vector<vector<int>> dist = {
        { 0,  2,  9, 10,  7},
        { 2,  0,  6,  4,  3},
        { 9,  6,  0,  8,  9},
        {10,  4,  8,  0,  5},
        { 7,  3,  9,  5,  0},
    };
    int n = dist.size();

    // MST (Kruskal manual): edges (0,1)=2, (1,4)=3, (1,3)=4, (1,2)=6. Total = 15.
    TSP2Approx tsp(n);
    tsp.add_mst_edge(0, 1, 2);
    tsp.add_mst_edge(1, 4, 3);
    tsp.add_mst_edge(1, 3, 4);
    tsp.add_mst_edge(1, 2, 6);

    int mst_weight = 2 + 3 + 4 + 6;
    int tour_cost = tsp.compute_tour(0, dist);

    cout << "MST weight: " << mst_weight << '\n';
    cout << "Batas 2*MST: " << 2 * mst_weight << '\n';
    cout << "Tour: ";
    tsp.print_tour();
    cout << "Tour cost: " << tour_cost << '\n';
    cout << "Optimal (manual): 27\n";
    cout << "Rasio approx: " << (double)tour_cost / 27.0 << '\n';
    return 0;
}

Output yang Dihasilkan:

MST weight: 15
Batas 2*MST: 30
Tour: 0 -> 1 -> 4 -> 3 -> 2 -> 0
Tour cost: 27
Optimal (manual): 27
Rasio approx: 1

Bedah Kode Baris-per-Baris #

1. add_mst_edge(u, v, w): tambahkan edge MST sebagai adjacency list. Catatan: input diasumsikan sudah MST; implementasi MST (Prim/Kruskal) lihat Chapter graph.
2. dfs(u): preorder traversal — catat node saat pertama kali dikunjungi. Child node di-adjacency list urutan input; urutan traversal mempengaruhi hasil tur.
3. compute_tour(start, dist): setelah DFS mengisi tour, hitung total jarak dengan menjumlahkan dist[tour[i]][tour[i+1]] ditambah dist[tour.back()][tour[0]] untuk menutup tur.
4. Triangle inequality: karena dist memenuhi d(a,c) ≤ d(a,b) + d(b,c), jarak lompatan langsung (mis. dari tour[3]=3 ke tour[4]=2) selalu ≤ jumlah edge MST yang “skip” — inilah yang menjamin ratio 2.
5. MST weight = 15: edges (0,1)=2, (1,4)=3, (1,3)=4, (1,2)=6. Total = 2+3+4+6 = 15.
6. Tour cost = 27: 0→1 (2) + 1→4 (3) + 4→3 (5) + 3→2 (8) + 2→0 (9) = 27. Bandingkan dengan 2·MST = 30 — tur 27 < 30 ✓.
7. Optimal = 27: verifikasi manual menunjukkan ada beberapa tur dengan cost 27 (mis. 0-2-3-4-1-0, 0-1-4-3-2-0). Approximation menemukan salah satu tur optimal → rasio = 1.0.
8. Catatan: rasio 1.0 adalah kasus terbaik; worst case rasio 2 tercapai untuk graph degenerate.

Set Cover Greedy (ln n)-Approximation #

Mekanisme: Greedy by Most Uncovered #

1. Selama ada elemen universe yang belum ter-cover:
   • Pilih set S_i yang menutupi paling banyak elemen belum-ter-cover.
   • Tandai elemen-elemen tersebut sebagai ter-cover.
2. Berhenti saat semua elemen ter-cover.

Analisis rasio: Misalkan OPT = jumlah set di solusi optimal. Setiap elemen dibayar oleh OPT set berbeda, jadi total “kredit” yang dialokasikan ke set optimal = n (jumlah elemen). Saat greedy memilih set yang menutupi k elemen baru, ia membayar “harga” 1/k per elemen (analisis standar). Total harga = n · (1/n + 1/(n-1) + ...) = H(n). Maka cost(ALG) ≤ H(n) · OPT di mana H(n) = 1 + 1/2 + 1/3 + ... + 1/n ≈ ln n.

Kode: Set Cover Greedy #

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

// Greedy Set Cover: pilih set yang menutupi paling banyak elemen yang belum tercover.
// Approximation ratio: H(n) = O(ln n) di mana n = ukuran universe.
class GreedySetCover {
    int universe_size_;
    vector<vector<int>> sets_;
public:
    GreedySetCover(int universe_size) : universe_size_(universe_size) {}

    void add_set(const vector<int>& s) { sets_.push_back(s); }

    // Mengembalikan indeks set yang dipilih.
    vector<int> solve() {
        unordered_set<int> covered;
        vector<int> chosen;
        while ((int)covered.size() < universe_size_) {
            int best_idx = -1;
            int best_uncovered = 0;
            for (int i = 0; i < (int)sets_.size(); ++i) {
                int cnt = 0;
                for (int x : sets_[i]) {
                    if (!covered.count(x)) ++cnt;
                }
                if (cnt > best_uncovered) {
                    best_uncovered = cnt;
                    best_idx = i;
                }
            }
            if (best_idx == -1) {
                cout << "Tidak bisa menutup universe dengan set yang tersedia!\n";
                break;
            }
            chosen.push_back(best_idx);
            for (int x : sets_[best_idx]) covered.insert(x);
        }
        return chosen;
    }
};

int main() {
    // Universe: {1,2,3,4,5,6,7,8}
    // Sets:
    //   0: {1,2,3,5,6,7}  — "bait": size 6, leaves {4,8}
    //   1: {1,2,3,4}      — optimal set 1
    //   2: {5,6,7,8}      — optimal set 2
    //   3: {4}            — singleton
    //   4: {8}            — singleton
    GreedySetCover gsc(8);
    gsc.add_set({1,2,3,5,6,7});  // idx 0
    gsc.add_set({1,2,3,4});     // idx 1
    gsc.add_set({5,6,7,8});     // idx 2
    gsc.add_set({4});           // idx 3
    gsc.add_set({8});           // idx 4

    auto chosen = gsc.solve();
    cout << "Greedy pilih " << chosen.size() << " set: ";
    for (int idx : chosen) cout << "S" << idx << ' ';
    cout << '\n';
    cout << "Optimal: { S1, S2 } = 2 set\n";
    cout << "Rasio: " << (double)chosen.size() / 2.0 << '\n';
    return 0;
}

Output yang Dihasilkan:

Greedy pilih 3 set: S0 S1 S2
Optimal: { S1, S2 } = 2 set
Rasio: 1.5

Bedah Kode Baris-per-Baris #

1. universe_size_ dan sets_: anggota universe diasumsikan integer 1..n (untuk demo). Implementasi umum menggunakan tipe elemen apa pun dengan unordered_set.
2. while ((int)covered.size() < universe_size_): loop sampai semua elemen ter-cover. Opsi alternatif: hitung remaining dan decrement saat menambah elemen baru.
3. for (int x : sets_[i]) { if (!covered.count(x)) ++cnt; }: hitung jumlah elemen belum-ter-cover untuk setiap set. Loop O(|S_i|) per set, total O(Σ|S_i|) per iterasi greedy.
4. if (cnt > best_uncovered): pilih set dengan uncovered count terbesar. Tie-breaking: set pertama (indeks terkecil) menang. Bisa juga break-tie dengan ukuran set terkecil atau biaya terendah.
5. chosen.push_back(best_idx): catat indeks set yang dipilih.
6. for (int x : sets_[best_idx]) covered.insert(x): tandai elemen yang baru ter-cover. unordered_set::insert amortized O(1) per elemen.
7. Verifikasi: greedy pertama pilih S0 (6 elemen uncovered, terbesar). Cover {1,2,3,5,6,7}. Remaining {4,8}. Lalu S1, S2, S3, S4 semuanya punya 1 uncovered — tie-breaking pilih S1 (indeks terkecil). Cover {4}. Lalu pilih S2 (1 uncovered, indeks lebih kecil dari S4). Cover {8}. Total 3 set. Optimal = 2 set ({S1, S2}). Rasio 3/2 = 1.5.

Kompleksitas dan Pemilihan #

Aplikasi dan Trade-off #

1. Vertex cover 2-approximation memberi solusi cepat untuk graph besar. Untuk graph kecil (n ≤ 50), branch-and-bound atau DP bitmask bisa memberi solusi exact.
2. TSP metric: banyak masalah nyata adalah metric (koordinat 2D, jarak Euclidean). Christofides algorithm (3/2-approx) lebih baik tetapi implementasi lebih kompleks (perlu perfect matching pada graph bipartit ganjil).
3. Set cover greedy: tidak ada algoritma polinomial dengan rasio (1-ε) · ln n (kecuali P = NP) — greedy sudah optimal dalam batas teoretis.

Ringkasan #

• Approximation ratio = jaminan formal cost(ALG) ≤ α · cost(OPT).
• Vertex cover 2-approximation: greedy edge-pick, tambah kedua endpoint per edge. Rasio 2, kompleksitas O(E).
• TSP metric 2-approximation: MST + preorder DFS walk, lalu tutup tur. Rasio 2, kompleksitas O(n²).
• Set cover greedy: pilih set dengan paling banyak uncovered. Rasio H(n) ≈ ln n, kompleksitas O(n · m).
• Pilih algoritma berdasarkan rasio yang dapat diterima vs kompleksitas implementasi.
• Untuk rasio mendekati 1 (mis. Knapsack), gunakan PTAS (Polynomial Time Approximation Scheme) — rasio 1 + ε dengan kompleksitas polinomial dalam n (tetapi eksponensial dalam 1/ε).