Tractability : practical approaches to hard problems / edited by Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli.

Includes bibliographical references.

Print version record.

An overview of the techniques developed to circumvent computational intractability, a key challenge in many areas of computer science.

Cover -- Tractability -- Title Page -- Copyright Page -- Contents -- Contributors -- Introduction -- Part 1: Graphical Structure -- 1 Treewidth and Hypertree Width -- 1.1 Treewidth -- 1.2 Hypertree width -- 1.3 Applications of hypertree width -- 1.4 Beyond (hyper)tree decompositions -- 1.5 Tractability frontiers (for CSPs) -- 1.6 Conclusion -- References -- 2 Perfect Graphs and Graphical Modeling -- 2.1 Berge Graphs and Perfect Graphs -- 2.2 Computational Properties of Perfect Graphs -- 2.3 Graphical Models -- 2.4 Nand Markov Random Fields

2.5 Maximum Weight Stable Set2.6 Tractable Graphical Models -- 2.7 Discussion -- 2.8 Acknowledgments -- 2.9 Appendix -- References -- Part 2: Language Restrictions -- 3 Submodular Function Maximization -- 3.1 Submodular Functions -- 3.2 Greedy Maximization of Submodular Functions -- 3.3 Beyond the Greedy Algorithm: Handling More Complex Constraints -- 3.4 Online Maximization of Submodular Functions -- 3.5 Adaptive Submodularity -- 3.6 Conclusions -- References -- 4 Tractable Valued Constraints -- 4.1 Introduction -- 4.2 Constraint Satisfaction Problems

4.3 Valued Constraint Satisfaction Problems4.4 Examples of Valued Constraint Languages -- 4.5 Expressive Power -- 4.6 Submodular Functions and Multimorphisms -- 4.7 Conservative Valued Constraint Languages -- 4.8 A General Algebraic Theory of Complexity -- 4.9 Conclusions and Open Problems -- References -- 5 Tractable Knowledge Representation Formalisms -- 5.1 Introduction -- 5.2 A Motivating Example -- 5.3 Negation Normal Form -- 5.4 Structured Decomposability -- 5.5 (X, Y)-Decompositions of Boolean Functions -- 5.6 Sentential Decision Diagrams

5.7 The Process of Compilation5.8 Knowledge Compilation in Probabilistic Reasoning -- 5.9 Conclusion -- References -- Part 3: Algorithms and their Analysis -- 6 Tree-Reweighted Message Passing -- 6.1 Introduction -- 6.2 Preliminaries -- 6.3 Sequential Tree-Reweighted Message Passing (TRW-S) -- 6.4 Analysis of the Algorithm -- 6.5 TRW-S with Monotonic Chains -- 6.6 Summary of the TRW-S Algorithm -- 6.7 Related Approaches -- 6.8 Conclusions and Discussion -- References -- 7 Tractable Optimization in Machine Learning -- 7.1 Introduction -- 7.2 Background

7.3 Smooth Convex Optimization7.4 Nonsmooth Convex Optimization -- 7.5 Stochastic Optimization -- 7.6 Summary -- References -- 8 Approximation Algorithms -- 8.1 Introduction -- 8.2 Combinatorial Algorithms -- 8.3 Linear Programming Based Algorithms -- 8.4 Semi-Definite Programming Based Algorithms -- 8.5 Algorithms for Special Instances -- 8.6 Metric Embeddings -- 8.7 Hardness of Approximation -- References -- 9 Kernelization Methods for Fixed-Parameter Tractability -- 9.1 Introduction -- 9.2 Basic Definitions -- 9.3 Classical Techniques

eBooks on EBSCOhost EBSCO eBook Subscription Academic Collection - Worldwide