Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SHERALI ADAMS:
TR16-017 | 24th December 2015
Georgios Stamoulis

#### Limitations of Linear Programming Techniques for Bounded Color Matchings

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>

TR17-154 | 12th October 2017
Christoph Berkholz

#### The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs

We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, ... more >>>

ISSN 1433-8092 | Imprint