MAX SAT approximation beyond the limits of polynomial-time approximation

Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch, Boris Konev

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

22 اقتباسات (Scopus)

ملخص

We describe approximation algorithms for (unweighted) MAX SAT with performance ratios arbitrarily close to 1, in particular, when performance ratios exceed the limits of polynomial-time approximation. Namely, given a polynomial-time α-approximation algorithm A0, we construct an (α+ε)-approximation algorithm A. The algorithm A runs in time of the order cεk, where k is the number of clauses in the input formula and c is a constant depending on α. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT and MAX 3SAT are also described. Taking known algorithms as A0 (for example, the Karloff-Zwick algorithm for MAX 3SAT), we obtain particular upper bounds on the running time of A.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)81-94
عدد الصفحات14
دوريةAnnals of Pure and Applied Logic
مستوى الصوت113
رقم الإصدار1-3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 27 ديسمبر 2001
منشور خارجيًانعم

بصمة

أدرس بدقة موضوعات البحث “MAX SAT approximation beyond the limits of polynomial-time approximation'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا