Approximation Algorithms for the Vertex Feedback Set Problem with Applications to Constraint Satisfaction and Bayesian Inference.
Reuven Bar-YehudaDan GeigerJoseph NaorRon M. RothPublished in: SODA (1994)
Keyphrases
- constraint satisfaction
- approximation algorithms
- bayesian inference
- constraint satisfaction problems
- minimum cost
- np hard
- set cover
- special case
- undirected graph
- probabilistic model
- prior information
- constraint relaxation
- constraint programming
- mathematical programming
- constraint propagation
- worst case
- computational complexity
- combinatorial problems
- learning algorithm
- machine learning