Approximation Algorithm
আসন্নীকরণ অ্যালগরিদম
NP-hard optimization সমস্যার জন্য polynomial সময়ে একটা প্রমাণিত-গ্যারান্টি সহ 'প্রায়-optimal' সমাধান দেয় এমন algorithm — নিখুঁত না, কিন্তু কতটা খারাপ হতে পারে তা গাণিতিকভাবে বাউন্ডেড।
also: approximation ratio, α-approximation
একটা algorithm A α-approximation যদি প্রতিটা instance x-এর
জন্য (minimization সমস্যায়) A(x) ≤ α · OPT(x), যেখানে OPT(x)
সত্যিকার অপটিমাল মান — যদিও নিজে সেটা খুঁজে বের করা exponential
সময় নিতে পারে।
উদাহরণ — Vertex Cover: greedy matching-based algorithm (একটা
uncovered edge বাছুন, দুই প্রান্তই কভারে যোগ করুন, তার সব edge
বাদ দিন) একটা 2-approximation — প্রমাণ matching-এর disjointness
ব্যবহার করে একটা lower bound তৈরি করে OPT-এর উপর।
PCP theorem-এর প্রভাব — inapproximability। কিছু সমস্যায় (Max-3-SAT,
Set Cover, Max-Clique) নির্দিষ্ট ratio-র চেয়ে ভালো approximation
নিজেই NP-hard প্রমাণিত — “gap-producing reduction” কৌশলে PCP
theorem থেকে। Max-3-SAT-এর সেরা সম্ভাব্য ratio ঠিক 7/8 (Håstad),
Set Cover-এর ln n (Feige) — দুটোই tight, matching upper আর lower
bound।
বাস্তব ব্যবহার: load balancing, network design, facility location — যেখানে SLA-জাতীয় worst-case গ্যারান্টি জরুরি, সেখানে heuristic-এর বদলে provable approximation algorithm ব্যবহৃত হয়।