Tractability : practical approaches to hard problems /
Tractability : practical approaches to hard problems /
edited by Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli.
- 1 online resource (xxii, 377 pages) : illustrations
Includes bibliographical references.
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
An overview of the techniques developed to circumvent computational intractability, a key challenge in many areas of computer science.
9781139177801 (electronic bk.) 113917780X (electronic bk.) 9781107731851 (electronic bk.) 1107731852 (electronic bk.)
016628827 Uk
Computational complexity.
Parameter estimation.
Complexité de calcul (Informatique)
Estimation d'un paramètre.
MATHEMATICS--General.
Computational complexity.
Parameter estimation.
Electronic books.
QA267.7 / T73 2014ab
511.3
Includes bibliographical references.
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
An overview of the techniques developed to circumvent computational intractability, a key challenge in many areas of computer science.
9781139177801 (electronic bk.) 113917780X (electronic bk.) 9781107731851 (electronic bk.) 1107731852 (electronic bk.)
016628827 Uk
Computational complexity.
Parameter estimation.
Complexité de calcul (Informatique)
Estimation d'un paramètre.
MATHEMATICS--General.
Computational complexity.
Parameter estimation.
Electronic books.
QA267.7 / T73 2014ab
511.3