Time-Approximation Trade-Offs for Learning Bayesian Networks

被引：0

作者：

Kundu, Madhumita ^{[1
]}

Parviainen, Pekka ^{[1
]}

Saurabh, Saket ^{[2
]}

机构：

[1] Univ Bergen, Bergen, Norway

[2] Univ Bergen, Inst Math Sci, Bergen, Norway

来源：

INTERNATIONAL CONFERENCE ON PROBABILISTIC GRAPHICAL MODELS | 2024年 / 246卷

关键词：

Bayesian Network Structure Learning; Parameterized Algorithms; Approximation Algorithms;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Bayesian network structure learning is an NP-hard problem. Furthermore, the problem remains hard even for various subclasses of graphs. Motivated by the hardness of exact learning, we study approximation algorithms for learning Bayesian networks. First, we propose a moderately exponential time algorithm with running time O(2(l/kn)) that has an approximation ratio l/k where n is the number of vertices and l and k are user-defined parameters with l <= k. That is, we give time-approximation trade-offs for learning Bayesian networks. Second, we present a polynomial time algorithm with an approximation ratio 1/d to find an optimal graph whose connected components have size at most d

引用

页码：486 / 497

页数：12