Lennart Sinjorgo \(\) We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices \(xx^{\mathrm{H}}\), where the elements of \(x \in \mathbb{C}^n\) are \(m\)th unit roots. These polytopes have applications in \({\text{MAX-3-CUT}}\), digital communication technology, angular synchronization and more generally, complex quadratic programming. For \({m=2}\), the complex cut polytope corresponds to the well-known cut … Read more
We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more
This paper is an in-depth analysis of the generalized $\vartheta$-number of a graph. The generalized $\vartheta$-number, $\vartheta_k(G)$, serves as a bound for both the $k$-multichromatic number of a graph and the maximum $k$-colorable subgraph problem. We present various properties of $\vartheta_k(G)$, such as that the series $(\vartheta_k(G))_k$ is increasing and bounded above by the order … Read more