کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437070 690071 2006 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Completeness in approximation classes beyond APX
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Completeness in approximation classes beyond APX
چکیده انگلیسی

We present a reduction that allows us to establish completeness results for several approximation classes mainly beyond APX. Using it, we extend one of the basic results of S. Khanna, R. Motwani, M. Sudan, and U. Vazirani (On syntactic versus computational views of approximability, SIAM J. Comput. 28 (1998) 164–191) by proving sufficient conditions for getting complete problems for the whole Log-APX, the class of problems approximable within ratios that are logarithms of the size of the instance, as well as for any approximability class beyond APX. We also introduce a new approximability class, called Poly-APX(Δ), dealing with graph-problems approximable with ratios functions of the maximum degree Δ of the input-graph. For this class also, using the proposed reduction, we establish complete problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 359, Issues 1–3, 14 August 2006, Pages 369-377