کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426420 | 686058 | 2015 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: Combinatorial and algorithmic applications
ترجمه فارسی عنوان
ماتریس های بولی با مقادیر ردیف / ستون ردیف و چندجملهای ثابت همگن: برنامه های ترکیبی و الگوریتمی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دائمی، الگوریتم، محدب چندجملهای ثابت، پیچیدگی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorithmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with boolean matrices with prescribed row and column sums within simply exponential multiplicative factor. This new algorithm is a particular instance of new polynomial time deterministic algorithms related to the multiple partial differentiation of polynomials given by evaluation oracles.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 240, February 2015, Pages 42–55
Journal: Information and Computation - Volume 240, February 2015, Pages 42–55
نویسندگان
Leonid Gurvits,