title   
  

Hardness and inapproximability results for minimum verification set and minimum path decision tree problems

Türker, Uraz Cengiz and Yenigün, Hüsnü (2012) Hardness and inapproximability results for minimum verification set and minimum path decision tree problems. [Working Paper / Technical Report] Sabanci University ID:10.5900/SU_FENS_WP.2012.19826

[img]
Preview
PDF (Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
315Kb

Abstract

Minimization of decision trees is a well studied problem. In this work, we introduce two new problems related to minimization of decision trees. The problems are called minimum verification set (MinVS) and minimum path decision tree (MinPathDT) problems. Decision tree problems ask the question "What is the unknown given object?". MinVS problem on the other hand asks the question "Is the unknown object z?", for a given object z. Hence it is not an identification, but rather a verification problem. MinPathDT problem aims to construct a decision tree where only the cost of the root-to-leaf path corresponding to a given object is minimized, whereas decision tree problems in general try to minimize the overall cost of decision trees considering all the objects. Therefore, MinVS and MinPathDT are seemingly easier problems. However, in this work we prove that MinVS and MinPathDT problems are both NP-complete and cannot be approximated within a factor in o(lg n) unless P = NP.

Item Type:Working Paper / Technical Report
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Q Science > QA Mathematics > QA076 Computer software
ID Code:19826
Deposited By:Hüsnü Yenigün
Deposited On:22 Oct 2012 16:42
Last Modified:22 Oct 2012 16:46

Repository Staff Only: item control page