Approximation অ্যালগরিদম — vertex cover, set cover আর metric TSP

১ · নিখুঁত না পেলে প্রমাণিত “যথেষ্ট ভালো” — approximation ratio

পর্ব ৬৪-এ দেখেছেন, vertex cover, set cover আর traveling salesman-এর মতো সমস্যা NP-hard: P ≠ NP হলে এদের নিখুঁত উত্তর বড় ইনপুটে দ্রুত বের করার কোনো উপায় নেই। পর্ব ৬৫-এ দেখেছেন বাস্তবে মানুষ কী করে — ছোট ইনপুটে brute force, বিশেষ গঠন কাজে লাগানো, আর heuristic. Heuristic প্রায়ই ভালো উত্তর দেয়, কিন্তু কতটা ভালো, তার কোনো নিশ্চয়তা দেয় না। এই পর্বের হাতিয়ার মাঝামাঝি: দ্রুত, আর সাথে একটি প্রমাণিত প্রতিশ্রুতি।

একটি approximation algorithm দুটি শর্ত মানে: (১) এটি polynomial time-এ চলে, আর (২) প্রতিটি ইনপুটে এর উত্তর সর্বোত্তম উত্তরের একটি নির্দিষ্ট গুণের মধ্যে থাকে। সর্বোত্তম উত্তরের মানকে লেখা হয় OPT, অ্যালগরিদমের উত্তরের মানকে ALG.

২ · OPT না জেনে কীভাবে প্রমাণ — নিম্নসীমার কৌশল

এখানে একটি আপাত-ধাঁধা আছে। “ALG ≤ 2 · OPT” প্রমাণ করতে OPT-এর সাথে তুলনা করতে হবে — অথচ OPT বের করাই তো NP-hard! সমাধান: OPT-এর সাথে সরাসরি তুলনা না করে একটি মধ্যবর্তী সংখ্যা LB ব্যবহার করুন, যার দুটি গুণ আছে — (ক) LB দ্রুত হিসাব করা যায়, আর (খ) যেকোনো সমাধান, তাই সর্বোত্তমটিও, অন্তত LB খরচ করে: LB ≤ OPT. তারপর অ্যালগরিদমের খরচকে LB দিয়ে বাঁধুন:

LB হলো একটি lower bound (নিম্নসীমা)। পুরো খেলাটা ভালো নিম্নসীমা খোঁজার খেলা — যত শক্ত (OPT-এর কাছাকাছি) নিম্নসীমা, তত ছোট ρ প্রমাণ করা যায়। Maximization-এ একই কাজ উল্টো দিকে: একটি upper bound UB ≥ OPT খুঁজে দেখান ALG ≥ UB / ρ. এই পর্বের প্রতিটি অ্যালগরিদমের পেছনে একটি করে নিম্নসীমা:

৩ · Vertex cover — matching দিয়ে ২-approximation

একটি ছোট শহরে সাতটি মোড় (A থেকে G) আর নয়টি রাস্তা। রাতে প্রতিটি রাস্তায় নজর রাখতে হবে। একজন নিরাপত্তারক্ষী একটি মোড়ে দাঁড়ালে সেই মোড় থেকে বের হওয়া সব রাস্তা দেখতে পান। সবচেয়ে কম কতজন রক্ষী দিয়ে সব রাস্তা পাহারা দেওয়া যায়? গ্রাফের ভাষায় মোড় = vertex, রাস্তা = edge, আর আমরা খুঁজছি সবচেয়ে ছোট vertex cover — এমন vertex-এর সেট, যা প্রতিটি edge-এর অন্তত এক প্রান্ত ছোঁয়। এটি Richard Karp-এর ১৯৭২ সালের ২১টি NP-complete সমস্যার একটি।

অ্যালগরিদমটি আশ্চর্য রকম সরল: রাস্তাগুলো যেকোনো ক্রমে একে একে দেখুন। যে রাস্তার দুই প্রান্তেই এখনো কোনো রক্ষী নেই, তার দুই প্রান্তেই একজন করে রক্ষী বসান। যে রাস্তার এক প্রান্তে রক্ষী আছে, সেটি এড়িয়ে যান। যেসব রাস্তার জন্য রক্ষী বসানো হলো, তাদের কোনো দুটি একই মোড় ছোঁয় না — অর্থাৎ তারা একটি matching. আর কোনো রাস্তাকে আর যোগ করা যায় না (প্রতিটি বাকি রাস্তার এক প্রান্ত ইতিমধ্যে ব্যবহৃত), তাই এটি একটি maximal matching.

Pseudocode — vertex cover by maximal matching (any vertex numbering)

ApproxVertexCover(G):
    C = { }                                  // guarded junctions
    for each edge (u, v) of G, in any order:
        if u not in C and v not in C:        // road still unguarded
            C = C + { u, v }                 // guard BOTH ends
    return C                                 // |C| = 2 |M| <= 2 OPT

রাস্তার ক্রম: A–B, A–C, B–C, B–D, C–E, D–E, D–F, E–G, F–G. নিচের ডায়াগ্রামে এগিয়ে দেখুন:

কেন ফলটি সর্বোচ্চ দ্বিগুণ — প্রমাণ

1. এটি cover: ধরুন শেষে কোনো edge (u, v) ঢাকা পড়েনি — u, v কেউই C-তে নেই। C শুধু বড় হয়, তাই যখন (u, v) দেখা হয়েছিল তখনও তারা C-তে ছিল না, আর তখনই অ্যালগরিদম দুটোকে যোগ করত। বিরোধ।
2. নিম্নসীমা: যে edge-গুলোর জন্য রক্ষী বসানো হয়েছে, তাদের সেট M একটি matching — নতুন edge তখনই নেওয়া হয়, যখন তার দুই প্রান্ত আগের কোনো matched edge-এ নেই। যেকোনো vertex cover-কে M-এর প্রতিটি edge-এর অন্তত এক প্রান্ত নিতে হয়, আর এই প্রান্তগুলো সব আলাদা (M-এর edge কোনো vertex ভাগ করে না)। তাই OPT ≥ |M|.
3. উপসংহার: |C| = 2|M| ≤ 2 · OPT. ∎

প্রতিটি edge একবার দেখা আর একটি boolean অ্যারে, তাই সময় Θ(V + E), বাড়তি জায়গা Θ(V). বাউন্ডটি tight: একটি তারার মতো গ্রাফে (কেন্দ্রে একটি মোড়, চারপাশে পাঁচটি) প্রথম রাস্তাতেই কেন্দ্র আর একটি পাতা নেওয়া হয় — ফল ২, অথচ শুধু কেন্দ্রই যথেষ্ট ছিল (OPT = ১)। সম্পূর্ণ bipartite গ্রাফ K_n,n-এ যেকোনো maximal matching perfect, তাই সেখানে ফল সবসময় 2n, অথচ OPT = n.

একটি সূক্ষ্ম পার্থক্য মনে রাখুন: maximal matching (আর বাড়ানো যায় না) লোভী এক পাসেই পাওয়া যায়; maximum matching (সবচেয়ে বড়) খুঁজতে পর্ব ৪৭-এর মতো augmenting path লাগে। Approximation-এর জন্য maximal-ই যথেষ্ট। Bipartite গ্রাফে আবার vertex cover নিখুঁতভাবেই সহজ — König-এর উপপাদ্য অনুযায়ী সেখানে সবচেয়ে ছোট cover = maximum matching-এর আকার।

৪ · কোডে vertex cover — approximation বনাম brute force

একটি approximation অ্যালগরিদম যাচাইয়ের সবচেয়ে সৎ উপায়: ছোট ইনপুটে brute force দিয়ে আসল OPT বের করে ratio ছাপানো। নিচের প্রোগ্রাম দুটি গ্রাফে এটি করে — আমাদের শহর আর পাঁচ পাতার একটি তারা। Brute force সব 2ⁿ টি vertex-উপসেট দেখে (n ≤ ২০ পর্যন্ত চলে); একটি উপসেট বিটমাস্ক হিসেবে রাখা, বিট v = 1 মানে মোড় v-তে রক্ষী।

#include <bit>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
using Edges = vector<pair<int, int>>;

Edges matchingCover(int n, const Edges& es) {              // 2-approximation
    vector<bool> taken(n, false); Edges matched;
    for (auto [u, v] : es)
        if (!taken[u] && !taken[v]) {                      // road still unguarded: guard both ends
            taken[u] = taken[v] = true; matched.push_back({u, v});
        }
    return matched;
}
unsigned exactCover(int n, const Edges& es) {             // brute force over all 2^n subsets
    unsigned best = (1u << n) - 1;
    for (unsigned m = 0; m < (1u << n); ++m) {
        if (popcount(m) >= popcount(best)) continue;
        bool ok = true;
        for (auto [u, v] : es) if (!(m >> u & 1) && !(m >> v & 1)) { ok = false; break; }
        if (ok) best = m;
    }
    return best;
}
void report(const char* name, int n, const Edges& es) {
    Edges matched = matchingCover(n, es); unsigned best = exactCover(n, es);
    int size = 2 * int(matched.size()), opt = popcount(best);
    printf("%s: matched", name);
    for (auto [u, v] : matched) printf(" %c-%c", 'A' + u, 'A' + v);
    printf("\n  optimum:");
    for (int v = 0; v < n; ++v) if (best >> v & 1) printf(" %c", 'A' + v);
    printf("\n  cover size %d, optimum %d, ratio %.2f\n", size, opt, double(size) / opt);
}
int main() {
    Edges town = {{0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {3,5}, {4,6}, {5,6}};
    Edges star = {{0,1}, {0,2}, {0,3}, {0,4}, {0,5}};
    report("town", 7, town);
    report("star", 6, star);
}

town: matched A-B C-E D-F
  optimum: A B E F
  cover size 6, optimum 4, ratio 1.50
star: matched A-B
  optimum: A
  cover size 2, optimum 1, ratio 2.00

def matching_cover(n, edges):                  # 2-approximation
    taken, matched = [False] * n, []
    for u, v in edges:
        if not taken[u] and not taken[v]:      # road still unguarded: guard both ends
            taken[u] = taken[v] = True
            matched.append((u, v))
    return matched

def exact_cover(n, edges):                     # brute force over all 2^n subsets
    best = (1 << n) - 1
    for m in range(1 << n):
        if bin(m).count("1") < bin(best).count("1") and \
           all(m >> u & 1 or m >> v & 1 for u, v in edges):
            best = m
    return best

def report(name, n, edges):
    matched = matching_cover(n, edges)
    best = exact_cover(n, edges)
    size, opt = 2 * len(matched), bin(best).count("1")
    print(f"{name}: matched", " ".join(f"{chr(65 + u)}-{chr(65 + v)}" for u, v in matched))
    print("  optimum:", " ".join(chr(65 + v) for v in range(n) if best >> v & 1))
    print(f"  cover size {size}, optimum {opt}, ratio {size / opt:.2f}")

town = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 6), (5, 6)]
star = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
report("town", 7, town)
report("star", 6, star)

town: matched A-B C-E D-F
  optimum: A B E F
  cover size 6, optimum 4, ratio 1.50
star: matched A-B
  optimum: A
  cover size 2, optimum 1, ratio 2.00

৫ · Set cover — greedy আর ln n-এর নিশ্চয়তা

একটি মোবাইল অপারেটর একটি উপজেলার ১৪টি ইউনিয়নে নেটওয়ার্ক দিতে চায়। জরিপে পাঁচটি সম্ভাব্য টাওয়ার-জায়গা পাওয়া গেছে; প্রতিটি থেকে কোন কোন ইউনিয়ন ঢাকা যায়, তা জানা। সবচেয়ে কম কয়টি টাওয়ার বসালে সব ইউনিয়ন নেটওয়ার্ক পায়? একই প্রশ্ন আসে কোচিং সেন্টারের শাখা বসাতে, প্রতিটি রোগের জন্য অন্তত একটি পরীক্ষা থাকে এমন সবচেয়ে ছোট ল্যাব-প্যানেল বানাতে, বা সব ফিচার ছোঁয় এমন সবচেয়ে ছোট test suite বাছতে।

আমাদের উদাহরণ: ইউনিয়ন u1–u7 উত্তর দিকে, u8–u14 দক্ষিণে। টাওয়ার North ঢাকে u1–u7, South ঢাকে u8–u14, X ঢাকে u1–u4 আর u8–u11 (৮টি), Y ঢাকে u5, u6, u12, u13 (৪টি), Z ঢাকে u7 আর u14. স্পষ্টতই North + South = ২টি টাওয়ারই যথেষ্ট। Greedy কী করে দেখুন — নিয়ম: প্রতিবার সেই সেটটি নিন, যা সবচেয়ে বেশি এখনো-না-ঢাকা উপাদান ঢাকে।

Pseudocode — greedy set cover

GreedySetCover(U, S1..Sm):
    covered = { };  picked = [ ]
    while covered != U:
        choose i maximising |Si - covered|          // most NEW elements
        k = |Si - covered|
        every element of Si - covered pays price 1/k  // for the proof only
        covered = covered + Si;  picked.append(i)
    return picked

প্রমাণ — pricing যুক্তি

প্রমাণের কৌশলটিকে বলে pricing (বা charging): greedy যখন একটি সেট নেয় যা k টি নতুন উপাদান ঢাকে, তখন সেই k টি উপাদানের প্রত্যেকের গায়ে ১/k দাম লিখে দিন। প্রতিটি বাছাই মোট ঠিক ১ দাম ভাগ করে, তাই greedy-র সেট-সংখ্যা = সব উপাদানের মোট দাম। এখন সর্বোত্তম সমাধানের যেকোনো একটি সেট S নিন, |S| = s. S-এর উপাদানগুলোকে greedy যে ক্রমে ঢেকেছে সেই ক্রমে সাজান: e₁, e₂, …, e_s. e_j ঢাকার ঠিক আগে S-এর অন্তত s − j + 1 টি উপাদান (e_j, …, e_s) এখনো খোলা — অর্থাৎ S নিজেই তখন অন্তত s − j + 1 টি নতুন উপাদান দিত। Greedy সবচেয়ে বেশি নতুন দেয় এমনটি বাছে, তাই সে অন্তত ততগুলো ঢেকেছে, আর e_j-এর দাম ≤ 1/(s − j + 1). যোগ করলে S-এর মোট দাম ≤ 1/s + … + 1/2 + 1 = H(s) ≤ H(d). সর্বোত্তম সমাধানের OPT টি সেট মিলে প্রতিটি উপাদান অন্তত একবার ঢাকে, তাই মোট দাম ≤ OPT · H(d). ∎

Greedy কতটা খারাপ হতে পারে: আমাদের উদাহরণটি একটি পরিবারের সদস্য। সারির দৈর্ঘ্য 2^k − 1 আর “ফাঁদ” সেটগুলোর আকার 2^k, 2^k−1, …, 2 (প্রতিটির অর্ধেক প্রতি সারিতে) নিলে greedy প্রতিবার ফাঁদ বাছে — মোট k টি সেট, অথচ OPT = ২. এখানে n = 2^k+1 − 2, তাই ratio k/2 ≈ (log₂ n)/2 — log n হারে বাড়ে। অর্থাৎ greedy-র ক্ষেত্রে ln n-এর ধাঁচের সীমা শুধু প্রমাণের দুর্বলতা নয়, সত্যিই ঘটে।

জটিলতা: প্রতি রাউন্ডে সব সেটের “নতুন উপাদান” গুনতে O(Σ|S_i|) লাগে, আর রাউন্ড সর্বোচ্চ min(m, n) টি — সরল বাস্তবায়নে O(min(m, n) · Σ|S_i|). নিচের কোডে প্রতিটি সেট একটি ১৪-বিটের মাস্ক, তাই “নতুন কয়টি” = popcount(mask & ~covered). প্রতিটি সেটের খরচ আলাদা হলে (weighted set cover) নিয়মটি হয় “নতুন প্রতি উপাদানে সবচেয়ে কম খরচ” — Chvátal (১৯৭৯) দেখান সেখানেও একই H(d) নিশ্চয়তা খাটে।

#include <bit>
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    const char* name[] = {"North", "South", "X", "Y", "Z"};          // candidate towers
    vector<vector<int>> covers = {{1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13, 14},
                                  {1, 2, 3, 4, 8, 9, 10, 11}, {5, 6, 12, 13}, {7, 14}};
    int k = int(covers.size());
    vector<unsigned> mask(k, 0);
    for (int i = 0; i < k; ++i) for (int u : covers[i]) mask[i] |= 1u << (u - 1);
    const unsigned all = (1u << 14) - 1;                              // unions 1..14

    unsigned covered = 0; int picks = 0;
    while (covered != all) {                                          // greedy: most new unions
        int best = -1, gain = 0;
        for (int i = 0; i < k; ++i) {
            int g = popcount(mask[i] & ~covered);
            if (g > gain) { gain = g; best = i; }
        }
        covered |= mask[best]; ++picks;
        printf("pick %-5s: %d new unions, each pays 1/%d\n", name[best], gain, gain);
    }
    int opt = k; unsigned optSet = 0;                                 // exact: try all 2^k choices
    for (unsigned s = 1; s < (1u << k); ++s) {
        unsigned u = 0;
        for (int i = 0; i < k; ++i) if (s >> i & 1) u |= mask[i];
        if (u == all && popcount(s) < opt) { opt = popcount(s); optSet = s; }
    }
    double h = 0;
    for (int i = 1; i <= 8; ++i) h += 1.0 / i;                        // H(largest set size)
    printf("greedy %d towers, optimum %d:", picks, opt);
    for (int i = 0; i < k; ++i) if (optSet >> i & 1) printf(" %s", name[i]);
    printf("\nratio %.2f, guarantee H(8) = %.2f\n", double(picks) / opt, h);
}

pick X    : 8 new unions, each pays 1/8
pick Y    : 4 new unions, each pays 1/4
pick Z    : 2 new unions, each pays 1/2
greedy 3 towers, optimum 2: North South
ratio 1.50, guarantee H(8) = 2.72

৬ · Metric TSP — MST দ্বিগুণ করে ঘোরা, তারপর শর্টকাট

একজন ডেলিভারি রাইডার গুদাম A থেকে বের হয়ে পাঁচটি ঠিকানায় (B–F) পার্সেল দিয়ে আবার A-তে ফিরবেন — সবচেয়ে কম পথ চালিয়ে। এটি traveling salesman problem (TSP). শহরের রাস্তা গ্রিডের মতো, তাই দুই ঠিকানার দূরত্ব = কয়টি ব্লক পূর্ব-পশ্চিমে + কয়টি উত্তর-দক্ষিণে: d = |x₁ − x₂| + |y₁ − y₂| (Manhattan দূরত্ব)। ঠিকানা: A(6, 0), B(6, 4), C(0, 4), D(2, 4), E(5, 0), F(1, 0).

এই দূরত্ব একটি গুরুত্বপূর্ণ শর্ত মানে — ত্রিভুজ অসমতা: যেকোনো u, v, w-এর জন্য d(u, w) ≤ d(u, v) + d(v, w); সরাসরি যাওয়া কখনো মাঝে থেমে যাওয়ার চেয়ে দীর্ঘ নয়। দূরত্ব প্রতিসম আর এই অসমতা মানলে সমস্যাটিকে বলে metric TSP. সমতলের সরলরেখা-দূরত্ব, Manhattan দূরত্ব, আর যেকোনো রাস্তার নেটওয়ার্কে সবচেয়ে ছোট পথের দূরত্ব (পর্ব ৪৪-এর Floyd–Warshall থেকে পাওয়া) — সবই metric. Metric TSP-ও NP-hard, কিন্তু এখানে approximation সম্ভব।

Pseudocode — MST doubling (2-approximation for metric TSP), start = depot

ApproxTSP(points, d):
    T = minimum spanning tree of the complete graph with weights d   // Prim, O(n^2)
    order = preorder DFS walk of T from the depot                       // first visits only
    return order + [depot]                                              // close the tour

কেন ২-approximation

1. OPT ≥ w(MST): সর্বোত্তম ট্যুর থেকে যেকোনো একটি edge মুছুন — যা থাকে তা সব শহর ছোঁয়া একটি path, অর্থাৎ একটি spanning tree. দূরত্ব ঋণাত্মক নয়, তাই OPT ≥ সেই tree-র ওজন ≥ w(MST).
2. পুরো হাঁটা = 2 · w(MST): DFS প্রতিটি tree-edge-এ একবার নামে, একবার ওঠে।
3. শর্টকাট দীর্ঘ করে না: হাঁটার মধ্যে u → … → w অংশ (মাঝের সবাই আগে দেখা) বদলে সরাসরি u → w নিলে, ত্রিভুজ অসমতা বারবার প্রয়োগ করে d(u, w) ≤ মাঝের পথের দৈর্ঘ্য। এই কাজকে বলে shortcutting, আর ফল হলো MST-এর preorder ক্রম।
4. তাই ALG ≤ 2 · w(MST) ≤ 2 · OPT. ∎

জটিলতা: সম্পূর্ণ গ্রাফে E = n(n − 1)/2, তাই অ্যারে-ভিত্তিক Prim Θ(n²), DFS Θ(n) — মোট Θ(n²) সময়। দূরত্ব দরকারমতো হিসাব করলে বাড়তি জায়গা Θ(n), পূর্ণ দূরত্ব-ম্যাট্রিক্স রাখলে Θ(n²).

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <numeric>
#include <vector>
using namespace std;
struct Pt { int x, y; };
vector<Pt> P = {{6,0}, {6,4}, {0,4}, {2,4}, {5,0}, {1,0}};          // A..F, A = depot
int d(int i, int j) { return abs(P[i].x - P[j].x) + abs(P[i].y - P[j].y); }  // street blocks
int cost(const vector<int>& t) {                                    // closed tour length
    int s = 0;
    for (size_t i = 0; i < t.size(); ++i) s += d(t[i], t[(i + 1) % t.size()]);
    return s;
}
int main() {
    int n = int(P.size()), mst = 0;
    vector<int> key(n, 1 << 30), par(n, -1); vector<bool> in(n, false);
    vector<vector<int>> kids(n); key[0] = 0;
    for (int it = 0; it < n; ++it) {                                 // dense Prim, O(n^2)
        int u = -1;
        for (int v = 0; v < n; ++v) if (!in[v] && (u < 0 || key[v] < key[u])) u = v;
        in[u] = true; mst += key[u];
        if (par[u] >= 0) { kids[par[u]].push_back(u); printf("MST edge %c-%c %d\n", 'A' + par[u], 'A' + u, key[u]); }
        for (int v = 0; v < n; ++v) if (!in[v] && d(u, v) < key[v]) { key[v] = d(u, v); par[v] = u; }
    }
    for (auto& k : kids) sort(k.begin(), k.end());                 // visit children A..F order
    vector<int> tour;                                               // preorder walk = shortcut tour
    auto dfs = [&](auto&& self, int u) -> void {
        tour.push_back(u);
        for (int c : kids[u]) self(self, c);
    }; dfs(dfs, 0);
    vector<int> best(n); iota(best.begin(), best.end(), 0); int opt = cost(best);
    vector<int> t = best;                                            // exact: all (n-1)! tours from A
    while (next_permutation(t.begin() + 1, t.end())) if (cost(t) < opt) { opt = cost(t); best = t; }
    auto show = [](const char* s, const vector<int>& t) {
        printf("%s", s); for (int v : t) printf("%c", 'A' + v); printf("A\n"); };
    printf("MST = %d, doubled walk = %d\n", mst, 2 * mst);
    show("MST tour ", tour); printf("  length %d\n", cost(tour));
    show("optimum  ", best); printf("  length %d, ratio %.2f\n", opt, double(cost(tour)) / opt);
}

MST edge A-E 1
MST edge A-B 4
MST edge B-D 4
MST edge D-C 2
MST edge E-F 4
MST = 15, doubled walk = 30
MST tour ABDCEFA
  length 28
optimum  ABDCFEA
  length 20, ratio 1.40

Christofides — ২ থেকে ১.৫

দুবার হাঁটার অপচয় কোথায়? প্রতিটি tree-edge দুবার চলা — শুধু যাতে প্রতিটি vertex-এর degree জোড় হয় আর একটি Euler circuit (প্রতিটি edge ঠিক একবার নিয়ে ঘোরা) পাওয়া যায়। Christofides-এর অ্যালগরিদম আরও সস্তায় degree জোড় করে: (১) MST T বানান; (২) T-তে বিজোড় degree-র vertex-গুলো O নিন — handshake lemma অনুযায়ী এদের সংখ্যা জোড়; (৩) O-এর ওপর সবচেয়ে কম ওজনের perfect matching M বের করুন; (৪) T + M-এ সব degree জোড়, তাই Euler circuit আছে; (৫) সেটি ধরে হাঁটুন আর শর্টকাট নিন।

কেন ১.৫: সর্বোত্তম ট্যুরকে শুধু O-এর vertex-গুলোতে শর্টকাট করুন — ত্রিভুজ অসমতায় দৈর্ঘ্য ≤ OPT. এই ছোট ট্যুরের edge-গুলো একটি-বাদ-একটি নিলে O-এর দুটি perfect matching পাওয়া যায়, যাদের মোট ≤ OPT, তাই হালকাটি ≤ OPT/2, আর w(M) ≤ OPT/2. ফলে ALG ≤ w(T) + w(M) ≤ OPT + OPT/2 = 1.5 · OPT. সময়ের প্রধান অংশ সাধারণ গ্রাফে minimum-weight perfect matching, O(n³). Nicos Christofides ১৯৭৬ সালে এটি প্রকাশ করেন; সোভিয়েত গবেষক Anatoliy Serdyukov স্বাধীনভাবে একই অ্যালগরিদম পান (১৯৭৮ সালে প্রকাশ), তাই এখন অনেকে একে Christofides–Serdyukov বলেন। প্রায় ৪৫ বছর কেউ ১.৫ ভাঙতে পারেননি। ২০২০ সালে Anna Karlin, Nathan Klein আর Shayan Oveis Gharan একটি randomized অ্যালগরিদমে দেখান ১.৫ − ε সম্ভব, যেখানে ε অবিশ্বাস্য রকম ছোট (প্রায় ১০^−৩৬) — ব্যবহারিক নয়, কিন্তু তাত্ত্বিক “দেয়াল” যে অভেদ্য নয়, তা প্রমাণিত।

ত্রিভুজ অসমতা না থাকলে — কোনো ধ্রুবক ratio নেই

সাধারণ TSP-এ (দূরত্ব যেকোনো) কোনো ধ্রুবক ρ-approximation নেই, যদি না P = NP (Sahni ও Gonzalez, ১৯৭৬)। প্রমাণ একটি reduction: ধরুন একটি ρ-approximation আছে। একটি গ্রাফ G (n vertex) নিন, যেখানে প্রশ্ন — Hamiltonian cycle (পর্ব ৫৬) আছে কি না, যা NP-complete. সম্পূর্ণ গ্রাফ বানান: G-এর edge-এর ওজন ১, বাকি জোড়ার ওজন ρn + 1. G-তে Hamiltonian cycle থাকলে OPT = n, তাই অ্যালগরিদম ≤ ρn দৈর্ঘ্যের ট্যুর দেবে — যাতে একটিও ভারী edge নেই — একটি থাকলেই দৈর্ঘ্য ρn ছাড়িয়ে যেত। না থাকলে প্রতিটি ট্যুরে অন্তত একটি ভারী edge, দৈর্ঘ্য > ρn. অর্থাৎ অ্যালগরিদমের ফল ≤ ρn কি না দেখেই Hamiltonian cycle-এর প্রশ্নের উত্তর polynomial সময়ে মিলত — P = NP. এই ধরনের যুক্তিকে বলে gap reduction: “হ্যাঁ” আর “না” ইনপুটের OPT-এর মধ্যে এত বড় ফাঁক তৈরি করা, যে ভালো approximation-ই সিদ্ধান্ত দিয়ে দেয়। খেয়াল করুন, ভারী edge-গুলো ত্রিভুজ অসমতা ভাঙে — metric শর্তই approximation-কে সম্ভব করে।

৭ · Load balancing আর knapsack — PTAS, FPTAS

List scheduling — Graham-এর ২ − ১/m

একটি পোশাক কারখানায় m টি সেলাই লাইন আর n টি অর্ডার; অর্ডার j শেষ করতে p_j ঘণ্টা লাগে, আর একটি অর্ডার একটিই লাইনে হয়। লক্ষ্য: সবচেয়ে ব্যস্ত লাইনের মোট সময় — makespan — যতটা সম্ভব কম রাখা। m = ২ হলেই এটি partition সমস্যা, NP-hard. Ronald Graham-এর ১৯৬৬ সালের list scheduling: অর্ডারগুলো যে ক্রমে আসে, প্রতিটি সেই মুহূর্তের সবচেয়ে কম ব্যস্ত লাইনে দিন। একটি min-heap-এ (পর্ব ২৩) লাইনের বোঝা রাখলে সময় O(n log m).

প্রমাণ: দুটি নিম্নসীমা — OPT ≥ max_j p_j (সবচেয়ে বড় অর্ডারটি কোনো লাইনে যাবেই) আর OPT ≥ (Σ p_j)/m (মোট কাজ m লাইনে ভাগ হলে কাউকে অন্তত গড়টুকু করতে হয়)। যে অর্ডার j সবার শেষে শেষ হয়, সেটি যখন দেওয়া হয়েছিল তখন তার লাইনটি সবচেয়ে কম ব্যস্ত ছিল, তাই তার শুরুর সময় ≤ (Σ p − p_j)/m. ফলে makespan ≤ (Σ p)/m + p_j(1 − 1/m) ≤ OPT + (1 − 1/m) · OPT = (2 − 1/m) · OPT. ∎ বড় অর্ডারগুলো আগে দিলে (Longest Processing Time first, LPT) Graham ১৯৬৯ সালে দেখান ratio ≤ 4/3 − 1/(3m); দাম শুধু একটি সর্ট, O(n log n).

Knapsack — যেকোনো কাছাকাছি, ইচ্ছেমতো

কিছু সমস্যায় আমরা আরও ভালো পাই: আপনি নিজে ε বেছে দিন (যেমন ০.০১), আর অ্যালগরিদম (1 + ε)-approximation দেবে — maximization-এ অন্তত (1 − ε) · OPT মানের উত্তর। ε যত ছোট, সময় তত বেশি। দুটি স্তর:

• PTAS (polynomial-time approximation scheme): প্রতিটি স্থির ε-এর জন্য সময় n-এর polynomial — কিন্তু ε-এর ওপর যেকোনোভাবে নির্ভর করতে পারে, যেমন O(n^1/ε). ε = ০.০১ হলে n¹⁰⁰ — তত্ত্বে polynomial, বাস্তবে অচল।
• FPTAS (fully polynomial): সময় n আর 1/ε দুটোরই polynomial, যেমন O(n³/ε).

0/1 knapsack-এর (পর্ব ৫৩) জন্য Ibarra আর Kim ১৯৭৫ সালে প্রথম FPTAS দেন। ধারণা: “মোট মান v-এর জন্য সবচেয়ে কম ওজন” — মান-ভিত্তিক এই DP-র সময় O(n · Σv), যা pseudo-polynomial; মানগুলো বড় হলেই সমস্যা। তাই মানগুলো ছোট করুন: K = ε · v_max / n নিন, প্রতিটি মান v_i-কে বদলে ⌊v_i / K⌋ করুন (সবচেয়ে বড়টি এখন ≤ n/ε), নতুন মানে DP চালিয়ে সেরা সেট নিন। সময় O(n · n · n/ε) = O(n³/ε). নিশ্চয়তা: গোল করায় প্রতিটি জিনিস সর্বোচ্চ K মান হারায়, তাই সর্বোত্তম সেটটি নতুন হিসাবে সর্বোচ্চ nK = ε · v_max হারায়। আমাদের সেটটি নতুন হিসাবে অন্তত তার সমান ভালো, তাই আসল মানে ALG ≥ OPT − ε · v_max ≥ (1 − ε) · OPT. এখানে ধরে নেওয়া হয়েছে প্রতিটি জিনিস একা ব্যাগে ধরে, তাই OPT ≥ v_max. ∎

উল্টো দিকে, যে সমস্যা ছোট সংখ্যাতেও NP-hard (strongly NP-hard, যেমন bin packing বা সাধারণ m-এর scheduling), তাদের FPTAS নেই, যদি না P = NP — কারণ FPTAS দিয়ে pseudo-polynomial নিখুঁত অ্যালগরিদম বানানো যেত।

৮ · কতটা কাছে যাওয়া অসম্ভব — inapproximability আর ইতিহাস

প্রতিটি NP-hard সমস্যা approximation-এর দিক থেকে সমান নয়। কিছুতে যত কাছে চান যাওয়া যায়, কিছুতে একটি সীমার নিচে নামা নিজেই NP-hard — এই দ্বিতীয় ধরনের ফলকে বলে inapproximability. মোটামুটি একটি সিঁড়ি:

এই ধরনের নিম্নসীমার বেশিরভাগের উৎস PCP theorem (১৯৯২; Arora ও Safra, এবং Arora, Lund, Motwani, Sudan ও Szegedy): NP-এর প্রতিটি “হ্যাঁ”-উত্তরের প্রমাণকে এমনভাবে লেখা যায়, যে একজন যাচাইকারী এলোমেলোভাবে মাত্র কয়েকটি (ধ্রুবক সংখ্যক) বিট পড়ে উচ্চ সম্ভাবনায় ভুল প্রমাণ ধরতে পারেন। এর একটি সমতুল্য রূপ: MAX-3SAT-এ (যত বেশি clause সত্য করা যায়) একটি নির্দিষ্ট ধ্রুবকের চেয়ে ভালো approximation NP-hard — তাই MAX-3SAT-এর PTAS নেই, যদি না P = NP. সেখান থেকে gap-রক্ষাকারী reduction দিয়ে অন্য সমস্যায় সীমা আসে। যে সমস্যায় কোনো ধ্রুবকের নিচে যাওয়া NP-hard, তাকে বলে APX-hard — vertex cover আর metric TSP দুটোই। Set cover-এ Feige (১৯৯৮) আর পরে Dinur ও Steurer (২০১৪) দেখান (1 − ε) ln n-এর চেয়ে ভালো করা কঠিন — অর্থাৎ ১৯৭৪ সালের সরল greedy প্রায় সেরা যা সম্ভব। Vertex cover-এ ২-এর চেয়ে ভালো কোনো অ্যালগরিদম আজও জানা নেই; Unique Games Conjecture (Khot, ২০০২) সত্য হলে ২ − ε-ও অসম্ভব (Khot ও Regev, ২০০৮)।

৯ · AI-এর যুগে approximation — ratio দাবি করা সহজ, প্রমাণ করা কঠিন

AI সহকারীকে “vertex cover-এর approximation দাও” বললে সে প্রায়ই সুন্দর কোড আর আত্মবিশ্বাসী একটি ratio লিখে দেবে। সমস্যা হলো, approximation-এর পুরো মূল্য প্রমাণে — আর ঠিক সেখানেই AI সবচেয়ে বেশি ভুল করে: degree-greedy-কে “২-approximation” বলা, MST-ট্যুরকে ত্রিভুজ অসমতা ছাড়াই খাটানো, বা “Christofides O(n²)” লিখে matching-এর খরচ ভুলে যাওয়া।

Approximation কোড যাচাইয়ের চেকলিস্ট

• ছোট ইনপুটে brute force দিয়ে OPT বের করে ratio ছাপিয়েছি, আর শত শত এলোমেলো ইনপুটে ratio কখনো ρ ছাড়ায়নি — stress testing
• উত্তরটি বৈধ কি না আলাদা করে পরীক্ষা করেছি (সব edge ঢাকা, সব উপাদান ঢাকা, ট্যুরে প্রতিটি শহর ঠিক একবার)
• প্রমাণের নিম্নসীমাটি নিজে লিখতে পারি, আর কোন শর্তে (metric, ঋণাত্মক নয় এমন ওজন) তা খাটে জানি
• Tight উদাহরণ (তারা-গ্রাফ, greedy-র ফাঁদ) চালিয়ে দেখেছি বাউন্ডটি সত্যিই ছোঁয়া যায়
• Edge case: edge-হীন গ্রাফ, একটি মাত্র শহর, সব দূরত্ব সমান, একই উপাদান অনেক সেটে
• AI-এর দেওয়া ratio-র জন্য প্রমাণ চেয়েছি; না পেলে counterexample খুঁজেছি