Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lift and Project:
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-157 | 13th October 2017
Monaldo Mastrolilli

High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts

Revisions: 2

Chvatal-Gomory (CG) cuts and the Bienstock-Zuckerberg hierarchy capture useful linear programs that the standard bounded degree Lasserre/Sum-of-Squares (SOS) hierarchy fails to capture.

In this paper we present a novel polynomial time SOS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low-degree ... more >>>

ISSN 1433-8092 | Imprint