Skip to content

 

Esamples are currently unavailable. We are working to correct the issues as quickly as possible. Thank you for your patience. 

Open global navigation

Cambridge University Press

AcademicLocation selectorSearch toggleMain navigation toggle
Cart
Register Sign in Wishlist

Tractability
Practical Approaches to Hard Problems

$110.00

Lucas Bordeaux, Youssef Hamadi, Pushmeet Kohli, Georg Gottlob, Gianluigi Greco, Francesco Scarcello, Tony Jebara, Andreas Krause, Daniel Golovin, Peter G. Jeavons, Stanislav Živný, Adnan Darwiche, Vladimir Kolmogorov, Suvrit Sra, Mohit Singh, Kunal Talwar, Fedor V. Fomin, Saket Saurabh, Lara Dolecek, Joao Marques-Silva, Ines Lynce, Nikolaj Bjørner, Leonardo de Moura
View all contributors
  • Date Published: March 2014
  • availability: In stock
  • format: Hardback
  • isbn: 9781107025196

$110.00
Hardback

Add to cart Add to wishlist

Other available formats:
eBook


Looking for an examination copy?

If you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact collegesales@cambridge.org providing details of the course you are teaching.

Description
Product filter button
Description
Contents
Resources
Courses
About the Authors
  • Classical computer science textbooks tell us that some problems are 'hard'. Yet many areas, from machine learning and computer vision to theorem proving and software verification, have defined their own set of tools for effectively solving complex problems. Tractability provides an overview of these different techniques, and of the fundamental concepts and properties used to tame intractability. This book will help you understand what to do when facing a hard computational problem. Can the problem be modelled by convex, or submodular functions? Will the instances arising in practice be of low treewidth, or exhibit another specific graph structure that makes them easy? Is it acceptable to use scalable, but approximate algorithms? A wide range of approaches is presented through self-contained chapters written by authoritative researchers on each topic. As a reference on a core problem in computer science, this book will appeal to theoreticians and practitioners alike.

    • Addresses a key issue in computer science theory and practice
    • Includes a wide range of techniques rarely presented in a single volume
    • Complements classical algorithms and existing literature
    Read more

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity

    ×

    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?

    ×

    Product details

    • Date Published: March 2014
    • format: Hardback
    • isbn: 9781107025196
    • length: 396 pages
    • dimensions: 253 x 178 x 20 mm
    • weight: 0.93kg
    • contains: 75 b/w illus.
    • availability: In stock
  • Table of Contents

    Contributors
    Introduction Lucas Bordeaux, Youssef Hamadi and Pushmeet Kohli
    Part I. Graphical Structure:
    1. Treewidth and hypertree width Georg Gottlob, Gianluigi Greco and Francesco Scarcello
    2. Perfect graphs and graphical modeling Tony Jebara
    Part II. Language Restrictions:
    3. Submodular function maximization Andreas Krause and Daniel Golovin
    4. Tractable valued constraints Peter G. Jeavons and Stanislav Živný
    5. Tractable knowledge representation formalisms Adnan Darwiche
    Part III. Algorithms and their Analysis:
    6. Tree-reweighted message passing Vladimir Kolmogorov
    7. Tractable optimization in machine learning Suvrit Sra
    8. Approximation algorithms Mohit Singh and Kunal Talwar
    9. Kernelization methods for fixed-parameter tractability Fedor V. Fomin and Saket Saurabh
    Part IV. Tractability in Some Specific Areas:
    10. Efficient submodular function minimization for computer vision Pushmeet Kohli
    11. Towards practical graph-based, iteratively decoded channel codes: insights through absorbing sets Lara Dolecek
    Part V. Heuristics:
    12. SAT solvers Joao Marques-Silva and Ines Lynce
    13. Tractability and modern satisfiability modulo theories solvers Nikolaj Bjørner and Leonardo de Moura.

  • Editors

    Lucas Bordeaux, Microsoft Research
    Lucas Bordeaux is a Senior Research Software Development Engineer at Microsoft Research, Cambridge, where he works on the design and applications of algorithms to solve hard inference problems.

    Youssef Hamadi, Microsoft Research
    Youssef Hamadi is a Senior Researcher at Microsoft Research, Cambridge. His work involves the practical resolution of large-scale real life problems set at the intersection of Optimization and Artificial Intelligence. His current research considers the design of complex systems based on multiple formalisms fed by different information channels which plan ahead and perform smart decisions. His current focus is on Autonomous Search, Parallel Search, and Propositional Satisfiability, with applications to Environmental Intelligence, Business Intelligence, and Software Verification.

    Pushmeet Kohli, Microsoft Research
    Pushmeet Kohli is a Research Scientist in the Machine Learning and Perception group at Microsoft Research, Cambridge. His research interests span the fields of Computer Vision, Machine Learning, Discrete Optimization, Game Theory, and Human-Computer Interaction with the overall aim of 'teaching' computers to understand the behaviour and intent of human users, and to correctly interpret (or 'See') objects and scenes depicted in colour/depth images or videos. In the context of tractability and optimization, Pushmeet has worked on developing adaptive combinatorial and message passing-based optimization algorithms that exploit the structure of problems to achieve improved performance.

    Contributors

    Lucas Bordeaux, Youssef Hamadi, Pushmeet Kohli, Georg Gottlob, Gianluigi Greco, Francesco Scarcello, Tony Jebara, Andreas Krause, Daniel Golovin, Peter G. Jeavons, Stanislav Živný, Adnan Darwiche, Vladimir Kolmogorov, Suvrit Sra, Mohit Singh, Kunal Talwar, Fedor V. Fomin, Saket Saurabh, Lara Dolecek, Joao Marques-Silva, Ines Lynce, Nikolaj Bjørner, Leonardo de Moura

Sign In

Please sign in to access your account

Cancel

Not already registered? Create an account now. ×

You are now leaving the Cambridge University Press website, your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Find content that relates to you

© Cambridge University Press 2014

Back to top

Are you sure you want to delete your account?

This cannot be undone.

Cancel Delete

Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

×
Please fill in the required fields in your feedback submission.
×