کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874260 | 686948 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximating decision trees with value dependent testing costs
ترجمه فارسی عنوان
تقریبا درخت تصمیم گیری با هزینه های آزمون وابسته به ارزش
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، درختان تصمیم گیری، الگوریتم های تقریبی، تجزیه و تحلیل الگوریتم ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the problem of evaluating a discrete function by adaptively querying the values of its variables. Reading the value of a variable is done at the expense of some cost, and the goal is to design a strategy (decision tree) with low cost for evaluating the function. In this paper, we study a variant of this problem in which the cost of reading a variable depends on the variable's value. We provide an O(logâ¡n) approximation algorithm for the minimization of the worst cost when every variable assumes at most two values, which is the best possible approximation under the assumption Pâ NP. For the general case where the variables may assume more than 2 values we present an n-approximation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 594-599
Journal: Information Processing Letters - Volume 115, Issues 6â8, JuneâAugust 2015, Pages 594-599
نویسندگان
Aline Saettler, Eduardo Laber, Ferdinando Cicalese,