Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Magen, Avner"'
Autor:
Magen, Avner, Zouzias, Anastasios
In this paper we develop algorithms for approximating matrix multiplication with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in\RR^{n \times p} be two matrices and \eps>0. We approximate the product A^\top B using two down-sampled s
Externí odkaz:
http://arxiv.org/abs/1005.2724
We study various SDP formulations for {\sc Vertex Cover} by adding different constraints to the standard formulation. We show that {\sc Vertex Cover} cannot be approximated better than $2-o(1)$ even when we add the so called pentagonal inequality con
Externí odkaz:
http://arxiv.org/abs/cs/0601011
Publikováno v:
In Computational Geometry: Theory and Applications 2008 39(1):24-29
Publikováno v:
In Theoretical Computer Science 2008 401(1):172-180
Publikováno v:
In Theoretical Computer Science 2005 348(2):251-261
Autor:
Linial, Nathan, Magen, Avner
Publikováno v:
In Journal of Combinatorial Theory, Series B July 2000 79(2):157-171
Autor:
Hatami, Hamed1 hamed@cs.toronto.edu, Magen, Avner1 avner@cs.toronto.edu, Markakis, Evangelos2 vangelis@cwi.nl
Publikováno v:
SIAM Journal on Discrete Mathematics. 2009, Vol. 23 Issue 1, p178-194. 17p.
Autor:
Magen, Avner, Zouzias, Anastasios
Publikováno v:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms.
In this paper we develop algorithms for approximating matrix multiplication with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in\RR^{n \times p} be two matrices and \eps>0. We approximate the product A^\top B using two down-sampled s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6c97a92e3291f3570ec44e3818968683
https://doi.org/10.1137/1.9781611973082.109
https://doi.org/10.1137/1.9781611973082.109
We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b92bc7ee154e70392a0e7291a1ad2fb4
Publikováno v:
Other University Web Domain
13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings
We initiate the study of on-line metric embeddings. In such an embedding we are given a sequence of n poin
We initiate the study of on-line metric embeddings. In such an embedding we are given a sequence of n poin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od________88::2f2cb149e15efcffe0ce2988b81f71f9
http://hdl.handle.net/1721.1/72043
http://hdl.handle.net/1721.1/72043