On finding optimal polytrees

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00087407" target="_blank" >RIV/00216224:14330/15:00087407 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2015.05.012" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2015.05.012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2015.05.012" target="_blank" >10.1016/j.tcs.2015.05.012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On finding optimal polytrees

Popis výsledku v původním jazyce

We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation.

Název v anglickém jazyce

On finding optimal polytrees

Popis výsledku anglicky

We study the NP-hard problem of finding a directed acyclic graph (DAG) on a given set of nodes so as to maximize a given scoring function. The problem models the task of inferring a probabilistic network from data, which has been studied extensively in the fields of artificial intelligence and machine learning. Several variants of the problem, where the output DAG is constrained in several ways, are NP-hard as well, for example when the DAG is required to have bounded in-degree, or when it is required to be a polytree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. In this paper, we generalize this polynomial-time result to polytrees that can be turned into a branching by deleting a constant number of arcs. Our algorithm stems from a matroid intersection formulation.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

592

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

10

Strana od-do

49-58

Kód UT WoS článku

000358624300005

EID výsledku v databázi Scopus

—