Approximating decision trees with value dependent testing costs
| Autor: | Aline Medeiros Saettler, Eduardo Sany Laber, Ferdinando Cicalese |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Mathematical optimization
Decision trees Decision tree Binary number Approximation algorithm Function (mathematics) Approximation algorithms Computer Science Applications Theoretical Computer Science Variable (computer science) Signal Processing Algorithms Analysis of algorithms Minification Value (mathematics) Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 115:594-599 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2015.02.006 |
| Popis: | 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 ? N P . For the general case where the variables may assume more than 2 values we present an n-approximation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect