Approximation Algorithm Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// 2-approximation for Vertex Cover on an undirected graph
5
// Idea: Scan edges; whenever we find an uncovered edge (u,v),
6
// add both u and v to the cover. The set of such edges is a matching,
7
// so |cover| <= 2 * |maximum matching| <= 2 * |optimal cover|.
8
9
vector<int> vertex_cover_2approx(int n, const vector<pair<int,int>>& edges) {
10
    vector<char> in_cover(n, false);
11
    for (auto [u, v] : edges) {
12
        if (!in_cover[u] && !in_cover[v]) {
13
            in_cover[u] = in_cover[v] = true; // pick both endpoints
14
        }
15
    }
16
    vector<int> cover;
17
    for (int i = 0; i < n; ++i) if (in_cover[i]) cover.push_back(i);
18
    return cover;
19
}
20
21
int main() {
22
    // Example graph (0-based): edges form a triangle 0-1-2-0
23
    int n = 4;
24
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3}};
25
26
    auto cover = vertex_cover_2approx(n, edges);
27
    cout << "Approximate vertex cover (size=" << cover.size() << "):";
28
    for (int v : cover) cout << ' ' << v;
29
    cout << "\n";
30
31
    // Verify every edge is covered (for demonstration)
32
    bool ok = true;
33
    vector<char> in_cover(n,false);
34
    for (int v : cover) in_cover[v] = true;
35
    for (auto [u,v] : edges) if (!in_cover[u] && !in_cover[v]) ok = false;
36
    cout << "All edges covered? " << (ok ? "yes" : "no") << "\n";
37
    return 0;
38
}
39

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Greedy Set Cover: repeatedly pick the set with the best (newly covered elements)/cost ratio.
5
// For unit costs, this is equivalent to picking the set that covers the largest number of uncovered elements.
6
// Guarantee: O(log n)-approximation (n = universe size) via harmonic number bound.
7
8
struct SetEntry {
9
    int id;
10
    double cost; // can be 1.0 for unit-cost
11
    vector<int> elems; // elements covered by this set (0..n-1)
12
};
13
14
vector<int> greedy_set_cover(int n, const vector<SetEntry>& sets) {
15
    vector<char> covered(n, false);
16
    int covered_cnt = 0;
17
    vector<int> chosen;
18
19
    // To speed up counting newly covered elements, maintain a per-set count updated each round.
20
    vector<vector<int>> elem_in_sets(n);
21
    for (const auto& s : sets) for (int e : s.elems) elem_in_sets[e].push_back(s.id);
22
23
    vector<int> remaining_new(sets.size(), 0);
24
    for (size_t j = 0; j < sets.size(); ++j) {
25
        remaining_new[j] = (int)sets[j].elems.size();
26
    }
27
28
    // Greedy iterations until all covered or no progress
29
    while (covered_cnt < n) {
30
        int best = -1; double best_score = -1.0; // score = newly_covered / cost
31
        for (size_t j = 0; j < sets.size(); ++j) {
32
            if (remaining_new[j] <= 0) continue; // no benefit
33
            double score = remaining_new[j] / max(1e-12, sets[j].cost);
34
            if (score > best_score) { best_score = score; best = (int)j; }
35
        }
36
        if (best == -1) break; // cannot cover remaining elements
37
38
        // Choose set 'best'
39
        chosen.push_back(best);
40
        // Update covered and remaining_new counts
41
        for (int e : sets[best].elems) {
42
            if (!covered[e]) {
43
                covered[e] = true;
44
                ++covered_cnt;
45
                // Elements newly covered reduce remaining_new for all sets containing e
46
                for (int sId : elem_in_sets[e]) {
47
                    if (remaining_new[sId] > 0) remaining_new[sId]--; 
48
                }
49
            }
50
        }
51
        // Mark this set as spent
52
        remaining_new[best] = 0;
53
    }
54
55
    // Optional: verify feasibility
56
    if (covered_cnt < n) {
57
        cerr << "Warning: Universe not fully covered (uncoverable elements?).\n";
58
    }
59
    return chosen;
60
}
61
62
int main() {
63
    // Universe U = {0,1,2,3,4}
64
    int n = 5;
65
    vector<SetEntry> sets;
66
    // Define sets with unit cost
67
    sets.push_back({0, 1.0, {0,1}});
68
    sets.push_back({1, 1.0, {1,2,3}});
69
    sets.push_back({2, 1.0, {3,4}});
70
    sets.push_back({3, 1.0, {0,2,4}});
71
72
    auto chosen = greedy_set_cover(n, sets);
73
    double total_cost = 0.0;
74
    cout << "Chosen sets:";
75
    for (int id : chosen) { cout << ' ' << id; total_cost += sets[id].cost; }
76
    cout << "\nTotal cost: " << total_cost << "\n";
77
78
    return 0;
79
}
80

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// FPTAS for 0/1 Knapsack using value scaling.
5
// Given n items (value v[i], weight w[i]) and capacity W, accuracy epsilon,
6
// we scale values by K = (epsilon * sum v_i) / n to limit DP state to O(n/epsilon).
7
// DP[v'] = minimum weight needed to achieve total scaled value v'.
8
// The achieved (rescaled) value is within (1 - epsilon) of OPT.
9
10
struct Item { long long value; long long weight; };
11
12
pair<long long,long long> knapsack_fptas(const vector<Item>& items, long long W, double epsilon) {
13
    int n = (int)items.size();
14
    long long sumV = 0; for (auto &it : items) sumV += it.value;
15
    if (sumV == 0) return {0LL, 0LL};
16
    if (epsilon <= 0) epsilon = 0.1; // fallback if user passes non-positive epsilon
17
18
    double Kd = (epsilon * (double)sumV) / max(1, n);
19
    if (Kd < 1e-9) Kd = 1e-9; // avoid division by zero
20
21
    vector<int> sv(n); // scaled values
22
    long long sumSV = 0;
23
    for (int i = 0; i < n; ++i) {
24
        sv[i] = (int)floor(items[i].value / Kd);
25
        if (sv[i] < 0) sv[i] = 0;
26
        sumSV += sv[i];
27
    }
28
    if (sumSV == 0) {
29
        // All values scaled to zero due to tiny K; pick any feasible item with max original value greedily
30
        long long bestV = 0, bestW = 0;
31
        for (auto &it : items) if (it.weight <= W && it.value > bestV) { bestV = it.value; bestW = it.weight; }
32
        return {bestV, bestW};
33
    }
34
35
    const long long INF = (1LL<<60);
36
    vector<long long> dp(sumSV + 1, INF);
37
    dp[0] = 0;
38
39
    // 1D DP over scaled value
40
    for (int i = 0; i < n; ++i) {
41
        for (long long v = sumSV - sv[i]; v >= 0; --v) {
42
            if (dp[v] == INF) continue;
43
            dp[v + sv[i]] = min(dp[v + sv[i]], dp[v] + items[i].weight);
44
        }
45
    }
46
47
    // Find best achievable scaled value within capacity W
48
    long long bestSV = 0;
49
    for (long long v = 0; v <= sumSV; ++v) if (dp[v] <= W) bestSV = v;
50
51
    long long approxValue = (long long) floor(bestSV * Kd); // lower bound on true value
52
    long long minWeightForBest = dp[bestSV];
53
    return {approxValue, minWeightForBest};
54
}
55
56
int main() {
57
    // Example: capacity W=10, items with (value, weight)
58
    vector<Item> items = {{10, 5}, {7, 3}, {12, 7}, {8, 4}};
59
    long long W = 10;
60
    double eps = 0.2; // 20% accuracy parameter
61
62
    auto [approxV, usedW] = knapsack_fptas(items, W, eps);
63
    cout << fixed << setprecision(2);
64
    cout << "Approximate value >= (1-" << eps << ")*OPT: " << approxV << " (weight used: " << usedW << ")\n";
65
    return 0;
66
}
67