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.

Approximating decision trees with value dependent testing costs

Cicalese, Ferdinando
2015-01-01

Abstract

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.
2015
Algorithms; Analysis of algorithms; Approximation algorithms; Decision trees
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/933097
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact