LFG Generation from Acyclic F-Structures is NP-Hard.
Jürgen WedekindRonald M. KaplanPublished in: Comput. Linguistics (2021)
Keyphrases
- np hard
- special case
- scheduling problem
- np complete
- approximation algorithms
- np hardness
- lower bound
- optimal solution
- worst case
- linear programming
- decision problems
- integer programming
- closely related
- data sets
- set cover
- minimum cost
- branch and bound algorithm
- constraint satisfaction problems
- computational complexity
- knapsack problem
- social networks
- database
- database schemes