Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Record link: 
http://hdl.handle.net/20.500.12708/58602
-
Title: 
Parameterized Complexity of Small Decision Tree Learning
-
Citation: 
Ordyniak, S., & Szeider, S. (2021). Parameterized Complexity of Small Decision Tree Learning. In Thirty-Fifth AAAI Conference on Artificial Intelligence (pp. 1–9). AAAI Press. http://hdl.handle.net/20.500.12708/58602
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Ordyniak, Sebastian 
Szeider, Stefan 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Thirty-Fifth AAAI Conference on Artificial Intelligence 
-
Date (published): 
2021
-
Event name: 
35th AAAI 2021 
-
Event date: 
2-Feb-2021 - 9-Feb-2021
-
Event place: 
virtual event, Unknown
-
Number of Pages: 
9
-
Publisher: 
AAAI Press, 35
-
Peer reviewed: 
Yes
-
Abstract: 
We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples. Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Informatik
Mathematik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

237
checked on Nov 23, 2023

Google ScholarTM

Check