The complexity of finding the maximum spanning DAG and other restrictions for DAG parsing of natural language
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingSimilar Papers 제목 키워드 기반
Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs
We study the Maximum Subgraph problem in deep dependency parsing. We consider two restrictions to deep dependency graphs: (a) 1-endpoint-crossing and (b) pagenumber-2. Our main contribution is an exact algorithm that obt…
Dependency ParsingSemantic Dependency ParsingParameterized Complexity Analysis of Randomized Search Heuristics
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach artic…
Combinatorial OptimizationEvolutionary AlgorithmsResource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise
Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make …
Maximum likelihood estimation of log-affine models using detailed-balanced reaction networks
A fundamental question in the field of molecular computation is what computational tasks a biochemical system can carry out. In this work, we focus on the problem of finding the maximum likelihood estimate (MLE) for log-…
Parameterized Complexity Results for Exact Bayesian Network Structure Learning
Bayesian network structure learning is the notoriously difficult problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case compl…
ARC