Zobrazeno 1 - 10
of 210
pro vyhledávání: '"Tunçel, Levent"'
We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and more generally, Max-Boo
Externí odkaz:
http://arxiv.org/abs/2406.18670
Autor:
Au, Yu Hin, Tunçel, Levent
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov\'{a}sz--Schrijver SDP operator $\text{LS}_+$, with a particular focus on finding and characterizing the smallest graphs with a given $\text{LS}_+$-rank (
Externí odkaz:
http://arxiv.org/abs/2401.01476
Autor:
Karimi, Mehdi, Tuncel, Levent
Quantum Relative Entropy (QRE) programming is a recently popular and challenging class of convex optimization problems with significant applications in quantum computing and quantum information theory. We are interested in modern interior point (IP)
Externí odkaz:
http://arxiv.org/abs/2312.07438
Autor:
Roshchina, Vera, Tunçel, Levent
Given any finite set of nonnegative integers, there exists a closed convex set whose facial dimension signature coincides with this set of integers, that is, the dimensions of its nonempty faces comprise exactly this set of integers. In this work, we
Externí odkaz:
http://arxiv.org/abs/2312.04419
A rational number is dyadic if it has a finite binary representation $p/2^k$, where $p$ is an integer and $k$ is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-po
Externí odkaz:
http://arxiv.org/abs/2309.04601
Autor:
Au, Yu Hin, Tunçel, Levent
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov\'asz-Schrijver SDP operator $\text{LS}_+$. In particular, we focus on a search for relatively small graphs with high $\text{LS}_+$-rank (i.e., the least
Externí odkaz:
http://arxiv.org/abs/2303.08971
Autor:
Romero, Julian, Tunçel, Levent
We study the computational efficiency of approaches, based on Hilbert's Nullstellensatz, which use systems of linear equations for detecting non-colorability of graphs having large girth and chromatic number. We show that for every non-$k$-colorable
Externí odkaz:
http://arxiv.org/abs/2212.05365
Autor:
Tunçel, Levent, Vandenberghe, Lieven
A convex cone is homogeneous if its automorphism group acts transitively on the interior of the cone, i.e., for every pair of points in the interior of the cone, there exists a cone automorphism that maps one point to the other. Cones that are homoge
Externí odkaz:
http://arxiv.org/abs/2211.00761
We study several variants of decomposing a symmetric matrix into a sum of a low-rank positive semidefinite matrix and a diagonal matrix. Such decompositions have applications in factor analysis and they have been studied for many decades. On the one
Externí odkaz:
http://arxiv.org/abs/2209.05678
A filter oracle for a clutter consists of a finite set $V$ along with an oracle which, given any set $X\subseteq V$, decides in unit time whether or not $X$ contains a member of the clutter. Let $\mathfrak{A}_{2n}$ be an algorithm that, given any clu
Externí odkaz:
http://arxiv.org/abs/2202.07299