অ্যাপ্রক্সিমেশন অ্যালগরিদম ও অ্যাপ্রক্সিমেশন রেশিও

১ · কেন আমাদের একটি সংখ্যা দরকার, শুধু "কাছাকাছি" যথেষ্ট নয়

L49-এ আমরা দেখেছি — একটি সমস্যা NP-হার্ড হলে (এবং $P \ne NP$ ধরে নিলে) পলিনোমিয়াল সময়ে সবসময় সঠিক উত্তর পাওয়ার কোনো নিশ্চয়তা নেই। একটি বাস্তবসম্মত পথ হলো এমন একটি পলিনোমিয়াল-সময়ের অ্যালগরিদম ডিজাইন করা যা অপটিমাল না হলেও, অপটিমামের কতটা কাছাকাছি থাকে তার একটি প্রমাণিত, গাণিতিক গ্যারান্টি দেয়। শুধু "সাধারণত ভালো ফল দেয়" বলাটা যথেষ্ট নয় — একজন অ্যালগরিদম ডিজাইনারের দরকার একটি সংখ্যা, এবং সেই সংখ্যাটি সব সম্ভাব্য ইনপুটে সত্য হতে হবে, শুধু টেস্ট করা কয়েকটাতে নয়।

২ · অ্যাপ্রক্সিমেশন রেশিওর আনুষ্ঠানিক সংজ্ঞা

ধরা যাক একটি অপটিমাইজেশন সমস্যার একটি ইনস্ট্যান্স $I$ আছে, $\text{OPT}(I)$ হলো সেই ইনস্ট্যান্সের সত্যিকারের অপটিমাল সমাধানের মান (cost বা value), এবং $\text{ALG}(I)$ হলো আমাদের পলিনোমিয়াল-সময়ের অ্যালগরিদম ALG-এর দেওয়া সমাধানের মান। একটি মিনিমাইজেশন সমস্যার জন্য (যেমন ভার্টেক্স কভার, TSP — যেখানে ছোট মান ভালো, এবং যেকোনো বৈধ সমাধানের মান অপটিমামের চেয়ে বড় বা সমান, অর্থাৎ $\text{ALG}(I) \ge \text{OPT}(I)$):

ALG একটি $k$-অ্যাপ্রক্সিমেশন অ্যালগরিদমk-Approximation Algorithmএমন একটি পলিনোমিয়াল-সময়ের অ্যালগরিদম যার সমাধানের মান, প্রতিটি সম্ভাব্য ইনস্ট্যান্সে, সত্যিকারের অপটিমামের একটি নির্দিষ্ট, প্রমাণিত ফ্যাক্টর $k$-এর বেশি খারাপ হয় না।, যদি একটি ধ্রুবক $k \ge 1$ থাকে যেন প্রতিটি ইনস্ট্যান্স $I$-এর জন্য:

লক্ষ্য করুন — এই অসমতাটি $I$-এর উপর নির্ভর করে না; $k$ একটি একক ধ্রুবক সংখ্যা যা সব সম্ভাব্য ইনপুটে কাজ করতে হবে। যদি কোনো একটি (এমনকি বিরল) ইনস্ট্যান্সে রেশিও $k$ ছাড়িয়ে যায়, তাহলে ALG একটি $k$-অ্যাপ্রক্সিমেশন নয় — এই একটি কাউন্টার-এক্সাম্পলই দাবিটি খণ্ডন করার জন্য যথেষ্ট (ঠিক যেমন L19-এ একটি কাউন্টার-এক্সাম্পল একটি গ্রিডি স্ট্র্যাটেজির সাধারণ সঠিকতার দাবি খণ্ডন করেছিল)।

ম্যাক্সিমাইজেশন সমস্যার জন্য (যেমন ম্যাক্স-কাট, ম্যাক্স-স্যাট — যেখানে বড় মান ভালো, এবং $\text{ALG}(I) \le \text{OPT}(I)$) দিকটা উল্টে যায়:

উভয় ক্ষেত্রেই $k=1$ মানে অ্যালগরিদমটি সবসময় ঠিক অপটিমাল — অর্থাৎ একটি সাধারণ এক্সাক্ট অ্যালগরিদম। $k$ যত বড় হয়, গ্যারান্টি তত দুর্বল। এই কোর্সে আমরা $k=2$-এর মতো ছোট, ধ্রুবক-ফ্যাক্টর গ্যারান্টি নিয়ে কাজ করব (L51-L52), যা ব্যবহারিকভাবে খুবই মূল্যবান।

৩ · একটি সম্পূর্ণ উদাহরণ — মাল্টিপ্রসেসর শিডিউলিং-এ গ্রিডি ২-অ্যাপ্রক্সিমেশন

ধারণাটি concrete করতে একটি সম্পূর্ণ, স্বয়ংসম্পূর্ণ উদাহরণ দেখা যাক (ভার্টেক্স কভার ও TSP-র জন্য পূর্ণাঙ্গ ট্রিটমেন্ট আসছে L51-L52-এ)। সমস্যা: $n$টি জব আছে, প্রতিটির প্রসেসিং টাইম $p_1,\dots,p_n$; $m$টি অভিন্ন মেশিন আছে। লক্ষ্য: জবগুলো মেশিনে ভাগ করে দেওয়া যাতে মেকস্প্যান (সবচেয়ে বেশি লোডেড মেশিনের সমাপ্তি সময়) মিনিমাইজ হয়। এই সমস্যাটি NP-হার্ড।

গ্রিডি লিস্ট শিডিউলিং: জবগুলো যেকোনো ক্রমে নিয়ে, প্রতিটি জবকে বর্তমানে সবচেয়ে কম লোডেড মেশিনে বসিয়ে দাও।

দাবি: এই গ্রিডি অ্যালগরিদম একটি ২-অ্যাপ্রক্সিমেশন, অর্থাৎ প্রতিটি ইনস্ট্যান্সে $\text{ALG}(I) \le 2 \cdot \text{OPT}(I)$।

প্রমাণ:

1. ধরা যাক মেশিন $M$ চূড়ান্ত মেকস্প্যান $L = \text{ALG}(I)$ অর্জন করেছে, এবং $p_j$ হলো $M$-এ শেষে বসানো জব।
2. যে মুহূর্তে $p_j$ বসানো হয়েছিল, $M$-এর লোড ছিল সব মেশিনের মধ্যে সর্বনিম্ন (নাহলে গ্রিডি অন্য মেশিন বেছে নিত) — ধরি এই লোড $L'$। তাই $L = L' + p_j$।
3. $L'$ যেহেতু $m$টি মেশিনের মধ্যে সর্বনিম্ন লোড, তাই সেই মুহূর্তে বসানো সব কাজের সমষ্টি $\ge m \cdot L'$। এই সমষ্টি মোট কাজ $W = \sum_i p_i$-এর বেশি হতে পারে না, আর $\text{OPT}(I) \ge W/m$ (কারণ অপটিমাম শিডিউলকেও একই $W$ কাজ $m$টি মেশিনে ভাগ করতে হয়)। তাই $L' \le W/m \le \text{OPT}(I)$।
4. $p_j \le \text{OPT}(I)$ — কারণ অপটিমাল শিডিউলেও জব $j$ কোনো-না-কোনো একটি মেশিনে বসে, আর সেই মেশিনের লোড (তাই মেকস্প্যান $\text{OPT}(I)$) অন্তত $p_j$ হতে বাধ্য।
5. যোগ করলে: $L = L' + p_j \le \text{OPT}(I) + \text{OPT}(I) = 2\,\text{OPT}(I)$।

এই যুক্তি যেকোনো ইনস্ট্যান্সের জন্য সত্য (কোনো নির্দিষ্ট $n$, $m$, বা $p_i$ ধরে নেওয়া হয়নি) — তাই এটি একটি প্রকৃত, সাধারণ প্রমাণ, কোনো উদাহরণ-ভিত্তিক পর্যবেক্ষণ নয়।

এবার প্রমাণটি সত্যিই ধরে কি না — সেটা ব্রুট-ফোর্স অপটিমাম-এর বিপরীতে কোডে যাচাই করা যাক:

import random
import itertools
import math

def greedy_list_scheduling(jobs, m):
    # প্রতিটি জব বর্তমানে সবচেয়ে কম-লোডেড মেশিনে বসানো হয়
    loads = [0] * m
    for p in jobs:
        i = loads.index(min(loads))
        loads[i] += p
    return max(loads)

def brute_force_makespan(jobs, m):
    # সব সম্ভাব্য জব-থেকে-মেশিন অ্যাসাইনমেন্ট (m^n) পরীক্ষা করে সত্যিকারের অপটিমাম বের করা
    n = len(jobs)
    best = math.inf
    for assignment in itertools.product(range(m), repeat=n):
        loads = [0] * m
        for job_idx, machine in enumerate(assignment):
            loads[machine] += jobs[job_idx]
        best = min(best, max(loads))
    return best

rng = random.Random(5)
worst_ratio = 0.0
print(f"{'trial':>5} | {'n':>3} | {'m':>3} | {'ALG':>5} | {'OPT':>5} | {'ratio':>6}")
for trial in range(12):
    n = rng.randint(3, 7)
    m = rng.randint(2, 3)
    jobs = [rng.randint(1, 20) for _ in range(n)]
    alg = greedy_list_scheduling(jobs, m)
    opt = brute_force_makespan(jobs, m)
    ratio = alg / opt
    worst_ratio = max(worst_ratio, ratio)
    print(f"{trial:>5} | {n:>3} | {m:>3} | {alg:>5} | {opt:>5} | {ratio:>6.2f}")
    assert ratio <= 2 + 1e-9, "২-অ্যাপ্রক্সিমেশন বাউন্ড ভঙ্গ হয়েছে!"

print(f"\nসর্বোচ্চ পর্যবেক্ষিত ratio (ALG/OPT): {worst_ratio:.2f} -- সবসময় <= 2.00")