[ACM Press the thirty-ninth annual ACM symposium - San Diego, California, USA (2007.06.11-2007.06.13)] Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 - Improved approximation for directed cut problems

[ACM Press the thirty-ninth annual ACM s

✍ Agarwal, Amit; Alon, Noga; Charikar, Moses S. 📂 Article 📅 2007 🏛 ACM Press ⚖ 265 KB

We present improved approximation algorithms for directed multicut and directed sparsest cut. The current best known approximation ratio for these problems is O(n 1/2 ). We obtain an Õ(n 11/23 )-approximation. Our algorithm works with the natural LP relaxation used in prior work. We use a randomized

[ACM Press the thirty-ninth annual ACM s

[ACM Press the thirty-ninth annual ACM symposium - San Diego, California, USA (2007.06.11-2007.06.13)] Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 - Computing crossing number in linear time

✍ Kawarabayashi, Ken-ichi; Reed, Buce 📂 Article 📅 2007 🏛 ACM Press ⚖ 212 KB

[ACM Press the thirty-ninth annual ACM s

[ACM Press the thirty-ninth annual ACM symposium - San Diego, California, USA (2007.06.11-2007.06.13)] Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 - Fourier meets möbius: fast subset convolution

✍ Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko 📂 Article 📅 2007 🏛 ACM Press ⚖ 191 KB

[ACM Press the thirty-ninth annual ACM s

[ACM Press the thirty-ninth annual ACM symposium - San Diego, California, USA (2007.06.11-2007.06.13)] Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 - The condition number of a randomly perturbed matrix

✍ Vu, Van H.; Tao, Terence 📂 Article 📅 2007 🏛 ACM Press ⚖ 240 KB

[ACM Press the thirty-fifth ACM symposiu

[ACM Press the thirty-fifth ACM symposium - San Diego, CA, USA (2003.06.09-2003.06.11)] Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03 - Polylogarithmic inapproximability

✍ Halperin, Eran; Krauthgamer, Robert 📂 Article 📅 2003 🏛 ACM Press ⚖ 253 KB

[ACM Press the thirty-sixth annual ACM s

[ACM Press the thirty-sixth annual ACM symposium - Chicago, IL, USA (2004.06.13-2004.06.16)] Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 - Approximating the cut-norm via Grothendieck's inequality

✍ Alon, Noga; Naor, Assaf 📂 Article 📅 2004 🏛 ACM Press 🌐 English ⚖ 212 KB