Approximating decision trees with value dependent testing costs

•The cost of a test in a decision tree can depend on its result (value).•We provide an O(log⁡(n)) approximation for binary tests and value dependent costs.•We provide an n approximation for multiway tests and value dependent costs. We study the problem of evaluating a discrete function by adaptively...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2015-06, Vol.115 (6-8), p.594-599
Main Authors: Saettler, Aline, Laber, Eduardo, Cicalese, Ferdinando
Format: Article
Language:English
Subjects:
Algorithms
Analysis of algorithms
Approximation
Approximation algorithms
Decision trees
Mathematical problems
Optimization algorithms
Studies
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•The cost of a test in a decision tree can depend on its result (value).•We provide an O(log⁡(n)) approximation for binary tests and value dependent costs.•We provide an n approximation for multiway tests and value dependent costs. 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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2015.02.006