Semialgebraic Proofs and Efficient Algorithm Design

Semialgebraic Proofs and Efficient Algorithm Design

Versandkostenfrei!
Versandfertig in 1-2 Wochen
101,99 €
inkl. MwSt.
PAYBACK Punkte
51 °P sammeln!
In the last two decades a link has been established that, in some cases, proof that a solution exists has enabled an algorithm to find that solution itself. This has had most effect on semialgebraic proof systems and linear and semidefinite programming. This monograph details the interplay between proof systems and efficient algorithm design and surveys the state-of-the-art for two of the most important semi-algebraic proof systems: Sherali-Adams and Sum-of-Squares. It provides the readers with a rigorous treatment of these systems both as proof systems, and as a general family of optimization...