Rabani, Yuval; Shpilka, Amir Corrigendum to: “Explicit construction of a small epsilon-net for linear threshold functions”. (English) Zbl 07617238 SIAM J. Comput. 51, No. 5, 1692-1702 (2022). MSC: 68Q99 52C07 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{A. Shpilka}, SIAM J. Comput. 51, No. 5, 1692--1702 (2022; Zbl 07617238) Full Text: DOI
Deng, Shichuan; Li, Jian; Rabani, Yuval Approximation algorithms for clustering with dynamic points. (English) Zbl 07576578 J. Comput. Syst. Sci. 130, 43-70 (2022). MSC: 68-XX PDFBibTeX XMLCite \textit{S. Deng} et al., J. Comput. Syst. Sci. 130, 43--70 (2022; Zbl 07576578) Full Text: DOI arXiv
Dvijotham, Krishnamurthy; Rabani, Yuval; Schulman, Leonard J. Convergence of incentive-driven dynamics in Fisher markets. (English) Zbl 1497.91170 Games Econ. Behav. 134, 361-375 (2022). MSC: 91B50 PDFBibTeX XMLCite \textit{K. Dvijotham} et al., Games Econ. Behav. 134, 361--375 (2022; Zbl 1497.91170) Full Text: DOI Link
Grandoni, Fabrizio; Ostrovsky, Rafail; Rabani, Yuval; Schulman, Leonard J.; Venkat, Rakesh A refined approximation for Euclidean \(k\)-means. (English) Zbl 1485.68268 Inf. Process. Lett. 176, Article ID 106251, 7 p. (2022). MSC: 68U05 68W25 90B80 PDFBibTeX XMLCite \textit{F. Grandoni} et al., Inf. Process. Lett. 176, Article ID 106251, 7 p. (2022; Zbl 1485.68268) Full Text: DOI arXiv
Bubeck, Sébastien; Coester, Christian; Rabani, Yuval The Randomized \(k\)-Server Conjecture is False! arXiv:2211.05753 Preprint, arXiv:2211.05753 [cs.DS] (2022). BibTeX Cite \textit{S. Bubeck} et al., ``The Randomized $k$-Server Conjecture is False!'', Preprint, arXiv:2211.05753 [cs.DS] (2022) Full Text: arXiv OA License
Bubeck, Sebastien; Rabani, Yuval; Sellke, Mark Online multiserver convex chasing and optimization. (English) Zbl 07788463 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2093-2104 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. Bubeck} et al., in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2093--2104 (2021; Zbl 07788463) Full Text: DOI arXiv
Banerjee, Sandip; Ostrovsky, Rafail; Rabani, Yuval Min-sum clustering (with outliers). (English) Zbl 07768361 Wootters, Mary (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 24th international conference, APPROX 2021, and 25th international conference, RANDOM 2021, University of Washington, Seattle, Washington, US (virtual conference), August 16–18, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 207, Article 16, 16 p. (2021). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{S. Banerjee} et al., LIPIcs -- Leibniz Int. Proc. Inform. 207, Article 16, 16 p. (2021; Zbl 07768361) Full Text: DOI arXiv
Rabani, Yuval; Schulman, Leonard J. The invisible hand of Laplace: the role of market structure in price convergence and oscillation. (English) Zbl 1470.91120 J. Math. Econ. 95, Article ID 102475, 14 p. (2021). MSC: 91B24 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{L. J. Schulman}, J. Math. Econ. 95, Article ID 102475, 14 p. (2021; Zbl 1470.91120) Full Text: DOI arXiv Link
Bubeck, Sébastien; Rabani, Yuval Parametrized metrical task systems. (English) Zbl 07758356 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 54, 14 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{S. Bubeck} and \textit{Y. Rabani}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 54, 14 p. (2020; Zbl 07758356) Full Text: DOI arXiv
Deng, Shichuan; Li, Jian; Rabani, Yuval Approximation algorithms for clustering with dynamic points. (English) Zbl 07651176 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 37, 15 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. Deng} et al., LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 37, 15 p. (2020; Zbl 07651176) Full Text: DOI
Ostrovsky, Rafail; Rabani, Yuval; Yousefi, Arman Strictly balancing matrices in polynomial time using Osborne’s iteration. (English) Zbl 1499.65139 Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 93, 11 p. (2018). MSC: 65F35 65F08 PDFBibTeX XMLCite \textit{R. Ostrovsky} et al., LIPIcs -- Leibniz Int. Proc. Inform. 107, Article 93, 11 p. (2018; Zbl 1499.65139) Full Text: DOI arXiv
Rabani, Yuval; Venkat, Rakesh Approximating sparsest cut in low rank graphs via embeddings from approximately low-dimensional spaces. (English) Zbl 1467.68145 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 21, 14 p. (2017). MSC: 68R12 68W25 90C22 90C35 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{R. Venkat}, LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 21, 14 p. (2017; Zbl 1467.68145) Full Text: DOI arXiv
Dvijotham, Krishnamurthy; Rabani, Yuval; Schulman, Leonard J. Convergence of incentive-driven dynamics in Fisher markets. (English) Zbl 1417.91215 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 554-567 (2017). MSC: 91B24 91B26 91B50 PDFBibTeX XMLCite \textit{K. Dvijotham} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 554--567 (2017; Zbl 1417.91215) Full Text: DOI
Ostrovsky, Rafail; Rabani, Yuval; Yousefi, Arman Matrix balancing in \(L_p\) norms: bounding the convergence rate of Osborne’s iteration. (English) Zbl 1412.65025 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 154-169 (2017). MSC: 65F35 65F08 PDFBibTeX XMLCite \textit{R. Ostrovsky} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 154--169 (2017; Zbl 1412.65025) Full Text: DOI arXiv
Naor, Assaf; Rabani, Yuval On Lipschitz extension from finite subsets. (English) Zbl 1372.46020 Isr. J. Math. 219, No. 1, 115-161 (2017). Reviewer: Mikhail Ostrovskii (Queens) MSC: 46B85 30L05 46A22 54C20 26A16 PDFBibTeX XMLCite \textit{A. Naor} and \textit{Y. Rabani}, Isr. J. Math. 219, No. 1, 115--161 (2017; Zbl 1372.46020) Full Text: DOI arXiv
Rabani, Yuval (ed.); Richa, Andrea (ed.); Saia, Jared (ed.); Woodruff, David P. (ed.) Editorial to the special issue on SODA’12. (English) Zbl 1398.00110 ACM Trans. Algorithms 12, No. 1, Article No. 1, 1 p. (2016). MSC: 00B25 68-06 68Wxx PDFBibTeX XMLCite \textit{Y. Rabani} (ed.) et al., ACM Trans. Algorithms 12, No. 1, Article No. 1, 1 p. (2016; Zbl 1398.00110) Full Text: DOI
Chatzigiannakis, Ioannis (ed.); Mitzenmacher, Michael (ed.); Rabani, Yuval (ed.); Sangiorgi, Davide (ed.) 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. (English) Zbl 1351.68012 LIPIcs – Leibniz International Proceedings in Informatics 55. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). xliii, 150 articles, not consecutively paged, electronic only, open access (2016). MSC: 68-06 68Nxx 68Qxx 00B25 PDFBibTeX XMLCite \textit{I. Chatzigiannakis} (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12--15, 2016. Proceedings. Wadern: Schloss Dagstuhl -- Leibniz Zentrum für Informatik (2016; Zbl 1351.68012) Full Text: Link Link
Avigdor-Elgrabli, Noa; Rabani, Yuval An improved competitive algorithm for reordering buffer management. (English) Zbl 1398.68687 ACM Trans. Algorithms 11, No. 4, Article No. 35, 15 p. (2015). MSC: 68W27 68W40 PDFBibTeX XMLCite \textit{N. Avigdor-Elgrabli} and \textit{Y. Rabani}, ACM Trans. Algorithms 11, No. 4, Article No. 35, 15 p. (2015; Zbl 1398.68687) Full Text: DOI
Avigdor-Elgrabli, Noa; Im, Sungjin; Moseley, Benjamin; Rabani, Yuval On the randomized competitive ratio of reordering buffer management with non-uniform costs. (English) Zbl 1422.68269 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 78-90 (2015). MSC: 68W20 68W27 90B35 PDFBibTeX XMLCite \textit{N. Avigdor-Elgrabli} et al., Lect. Notes Comput. Sci. 9134, 78--90 (2015; Zbl 1422.68269) Full Text: DOI
Li, Jian; Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya Learning arbitrary statistical mixtures of discrete distributions. (English) Zbl 1321.68407 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 743-752 (2015). MSC: 68T05 68W20 PDFBibTeX XMLCite \textit{J. Li} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 743--752 (2015; Zbl 1321.68407) Full Text: DOI arXiv Link
Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya Learning mixtures of arbitrary distributions over large discrete domains. (English) Zbl 1366.68247 Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 207-223 (2014). MSC: 68T05 68W20 PDFBibTeX XMLCite \textit{Y. Rabani} et al., in: Proceedings of the 5th conference on innovations in theoretical computer science, ITCS'14, Princeton, NJ, USA, January 11--14, 2014. New York, NY: Association for Computing Machinery (ACM). 207--223 (2014; Zbl 1366.68247) Full Text: DOI arXiv
Avigdor-Elgrabli, Noa; Rabani, Yuval A constant factor approximation algorithm for reordering buffer management. (English) Zbl 1422.68285 Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 973-984 (2013). MSC: 68W25 68W40 90B35 PDFBibTeX XMLCite \textit{N. Avigdor-Elgrabli} and \textit{Y. Rabani}, in: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6--8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 973--984 (2013; Zbl 1422.68285) Full Text: DOI arXiv
Ostrovsky, Rafail; Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya The effectiveness of Lloyd-type methods for the \(k\)-means problem. (English) Zbl 1281.68229 J. ACM 59, No. 6, Article No. 28, 22 p. (2012). MSC: 68W20 68W25 68T20 68T10 PDFBibTeX XMLCite \textit{R. Ostrovsky} et al., J. ACM 59, No. 6, Article No. 28, 22 p. (2012; Zbl 1281.68229) Full Text: DOI
Cevallos, Alfonso; Fehr, Serge; Ostrovsky, Rafail; Rabani, Yuval Unconditionally-secure robust secret sharing with compact shares. (English) Zbl 1297.94116 Pointcheval, David (ed.) et al., Advances in cryptology – EUROCRYPT 2012. 31st annual international conference on the theory and applications of cryptographic techniques, Cambridge, UK, April 15–19, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29010-7/pbk). Lecture Notes in Computer Science 7237, 195-208 (2012). MSC: 94A62 PDFBibTeX XMLCite \textit{A. Cevallos} et al., Lect. Notes Comput. Sci. 7237, 195--208 (2012; Zbl 1297.94116) Full Text: DOI
Arora, Sanjeev; Lovász, László; Newman, Ilan; Rabani, Yuval; Rabinovich, Yuri; Vempala, Santosh Local versus global properties of metric spaces. (English) Zbl 1291.90195 SIAM J. Comput. 41, No. 1, 250-271 (2012). MSC: 90C27 05C85 46B85 PDFBibTeX XMLCite \textit{S. Arora} et al., SIAM J. Comput. 41, No. 1, 250--271 (2012; Zbl 1291.90195) Full Text: DOI Link
Karnin, Zohar S.; Rabani, Yuval; Shpilka, Amir Explicit dimension reduction and its applications. (English) Zbl 1253.68154 SIAM J. Comput. 41, No. 1, 219-249 (2012). MSC: 68Q17 PDFBibTeX XMLCite \textit{Z. S. Karnin} et al., SIAM J. Comput. 41, No. 1, 219--249 (2012; Zbl 1253.68154) Full Text: DOI
Rabani, Yuval (ed.) Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. (English) Zbl 1258.68014 Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-211-5). 1753 p., electronic. (2012). MSC: 68-06 05-06 68R10 68P05 05C85 68W05 00B25 PDFBibTeX XMLCite \textit{Y. Rabani} (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (2012; Zbl 1258.68014) Full Text: Link
Calinescu, Gruia; Chakrabarti, Amit; Karloff, Howard; Rabani, Yuval An improved approximation algorithm for Resource Allocation. (English) Zbl 1295.68209 ACM Trans. Algorithms 7, No. 4, Article No. 48, 7 p. (2011). MSC: 68W25 68W40 90B05 90C29 PDFBibTeX XMLCite \textit{G. Calinescu} et al., ACM Trans. Algorithms 7, No. 4, Article No. 48, 7 p. (2011; Zbl 1295.68209) Full Text: DOI
Karloff, Howard; Korn, Flip; Makarychev, Konstantin; Rabani, Yuval On parsimonious explanations for 2-D tree- and linearly-ordered data. (English) Zbl 1230.68067 Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 332-343, electronic only (2011). MSC: 68P15 68P20 68T30 68Q17 68W25 68W20 PDFBibTeX XMLCite \textit{H. Karloff} et al., LIPIcs -- Leibniz Int. Proc. Inform. 9, 332--343 (2011; Zbl 1230.68067) Full Text: DOI Link
Azar, Yossi; Devanur, Nikhil R.; Jain, Kamal; Rabani, Yuval Monotonicity in bargaining networks. (English) Zbl 1288.91007 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 817-826 (2010). MSC: 91A10 91B26 91B10 PDFBibTeX XMLCite \textit{Y. Azar} et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 817--826 (2010; Zbl 1288.91007)
Avigdor-Elgrabli, Noa; Rabani, Yuval An improved competitive algorithm for reordering buffer management. (English) Zbl 1288.68101 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 13-21 (2010). MSC: 68Q25 68W27 68W25 90C05 PDFBibTeX XMLCite \textit{N. Avigdor-Elgrabli} and \textit{Y. Rabani}, in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 13--21 (2010; Zbl 1288.68101)
Rabani, Yuval; Shpilka, Amir Explicit construction of a small \(\epsilon\)-net for linear threshold functions. (English) Zbl 1209.68347 SIAM J. Comput. 39, No. 8, 3501-3520 (2010); corrigendum ibid. 51, No. 5, 1506-1516 (2022). MSC: 68Q99 52C07 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{A. Shpilka}, SIAM J. Comput. 39, No. 8, 3501--3520 (2010; Zbl 1209.68347) Full Text: DOI
Rabani, Yuval; Scalosub, Gabriel Bicriteria approximation tradeoff for the node-cost budget problem. (English) Zbl 1445.68354 ACM Trans. Algorithms 5, No. 2, Article No. 19, 14 p. (2009). MSC: 68W25 90C35 90C59 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{G. Scalosub}, ACM Trans. Algorithms 5, No. 2, Article No. 19, 14 p. (2009; Zbl 1445.68354) Full Text: DOI
Ostrovsky, Rafail; Rabani, Yuval; Schulman, Leonard J. Error-correcting codes for automatic control. (English) Zbl 1367.94377 IEEE Trans. Inf. Theory 55, No. 7, 2931-2941 (2009). MSC: 94B05 93E10 PDFBibTeX XMLCite \textit{R. Ostrovsky} et al., IEEE Trans. Inf. Theory 55, No. 7, 2931--2941 (2009; Zbl 1367.94377) Full Text: DOI
Rabani, Yuval; Shpilka, Amir Explicit construction of a small epsilon-net for linear threshold functions. (English) Zbl 1304.94136 Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 649-658 (2009). MSC: 94C10 68U05 94B15 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{A. Shpilka}, in: Proceedings of the 41st annual ACM symposium on theory of computing, STOC '09. Bethesda, MD, USA, May 31 -- June 2, 2009. New York, NY: Association for Computing Machinery (ACM). 649--658 (2009; Zbl 1304.94136) Full Text: DOI
Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair Low distortion maps between point sets. (English) Zbl 1205.68179 SIAM J. Comput. 39, No. 4, 1617-1636 (2009). MSC: 68Q25 68W25 PDFBibTeX XMLCite \textit{C. Kenyon} et al., SIAM J. Comput. 39, No. 4, 1617--1636 (2009; Zbl 1205.68179) Full Text: DOI
Karloff, Howard; Khot, Subhash; Mehta, Aranyak; Rabani, Yuval On earthmover distance, metric labeling, and 0-extension. (English) Zbl 1200.68121 SIAM J. Comput. 39, No. 2, 371-387 (2009). MSC: 68Q17 68W25 PDFBibTeX XMLCite \textit{H. Karloff} et al., SIAM J. Comput. 39, No. 2, 371--387 (2009; Zbl 1200.68121) Full Text: DOI
Krauthgamer, Robert; Rabani, Yuval Improved lower bounds for embeddings into \(L_1\). (English) Zbl 1191.68869 SIAM J. Comput. 38, No. 6, 2487-2498 (2009). MSC: 68W25 90C22 05C85 PDFBibTeX XMLCite \textit{R. Krauthgamer} and \textit{Y. Rabani}, SIAM J. Comput. 38, No. 6, 2487--2498 (2009; Zbl 1191.68869) Full Text: DOI
Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya Approximation algorithms for labeling hierarchical taxonomies. (English) Zbl 1192.68916 Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 671-680 (2008). MSC: 68W25 05C85 68T30 90B80 PDFBibTeX XMLCite \textit{Y. Rabani} et al., in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2008, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 671--680 (2008; Zbl 1192.68916)
Rabani, Yuval; Scalosub, Gabriel Bicriteria approximation tradeoff for the node-cost budget problem. (English) Zbl 1155.68585 Gudmundsson, Joachim (ed.), Algorithm theory – SWAT 2008. 11th Scandinavian workshop on algorithm theory, Gothenburg, Sweden, July 2–4, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69900-2/pbk). Lecture Notes in Computer Science 5124, 90-101 (2008). MSC: 68W25 90C35 90C59 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{G. Scalosub}, Lect. Notes Comput. Sci. 5124, 90--101 (2008; Zbl 1155.68585) Full Text: DOI
Ostrovsky, Rafail; Rabani, Yuval Low distortion embeddings for edit distance. (English) Zbl 1326.68327 J. ACM 54, No. 5, Article No. 23, 16 p. (2007). MSC: 68W05 68P20 68Q25 68W40 PDFBibTeX XMLCite \textit{R. Ostrovsky} and \textit{Y. Rabani}, J. ACM 54, No. 5, Article No. 23, 16 p. (2007; Zbl 1326.68327) Full Text: DOI
Moss, A.; Rabani, Y. Approximation algorithms for constrained node weighted Steiner tree problems. (English) Zbl 1137.68063 SIAM J. Comput. 37, No. 2, 460-481 (2007). MSC: 68W25 90C27 90C35 PDFBibTeX XMLCite \textit{A. Moss} and \textit{Y. Rabani}, SIAM J. Comput. 37, No. 2, 460--481 (2007; Zbl 1137.68063) Full Text: DOI
Karloff, Howard; Khot, Subhash; Mehta, Aranyak; Rabani, Yuval On earthmover distance, metric labeling, and 0-extension. (English) Zbl 1301.68148 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 547-556 (2006). MSC: 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{H. Karloff} et al., in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21--23, 2006. New York, NY: ACM Press. 547--556 (2006; Zbl 1301.68148) Full Text: DOI
Krauthgamer, Robert; Rabani, Yuval Improved lower bounds for embeddings into \(L_1\). (English) Zbl 1192.90178 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 1010-1017 (2006). MSC: 90C27 05C85 54E35 PDFBibTeX XMLCite \textit{R. Krauthgamer} and \textit{Y. Rabani}, in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1010--1017 (2006; Zbl 1192.90178) Full Text: DOI
Arora, Sanjeev; Lovász, László; Newman, Ilan; Rabani, Yuval; Rabinovich, Yuri; Vempala, Santosh Local versus global properties of metric spaces (extended abstract). (English) Zbl 1192.90155 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 41-50 (2006). MSC: 90C27 05C85 PDFBibTeX XMLCite \textit{S. Arora} et al., in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 41--50 (2006; Zbl 1192.90155) Full Text: DOI
Chuzhoy, Julia; Ostrovsky, Rafail; Rabani, Yuval Approximation algorithms for the job interval selection problem and related scheduling problems. (English) Zbl 1278.90146 Math. Oper. Res. 31, No. 4, 730-738 (2006). MSC: 90B35 PDFBibTeX XMLCite \textit{J. Chuzhoy} et al., Math. Oper. Res. 31, No. 4, 730--738 (2006; Zbl 1278.90146) Full Text: DOI Link
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D. On the hardness of approximating Multicut and Sparsest-Cut. (English) Zbl 1132.68418 Comput. Complexity 15, No. 2, 94-114 (2006). MSC: 68Q17 90C60 PDFBibTeX XMLCite \textit{S. Chawla} et al., Comput. Complexity 15, No. 2, 94--114 (2006; Zbl 1132.68418) Full Text: DOI
Langberg, Michael; Rabani, Yuval; Swamy, Chaitanya Approximation algorithms for graph homomorphism problems. (English) Zbl 1155.68581 Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 176-187 (2006). MSC: 68W25 05C85 PDFBibTeX XMLCite \textit{M. Langberg} et al., Lect. Notes Comput. Sci. 4110, 176--187 (2006; Zbl 1155.68581) Full Text: DOI
Chuzhoy, Julia; Rabani, Yuval Approximating \(k\)-median with non-uniform capacities. (English) Zbl 1297.68262 Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 952-958 (2005). MSC: 68W25 90B80 PDFBibTeX XMLCite \textit{J. Chuzhoy} and \textit{Y. Rabani}, in: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23--25, 2005. New York, NY: ACM Press. 952--958 (2005; Zbl 1297.68262)
Ostrovsky, Rafail; Rabani, Yuval Low distortion embeddings for edit distance. (English) Zbl 1192.68835 STOC’05: Proceedings of the 37th annual ACM symposium on theory of computing, Baltimore, MD, USA, May 22–24, 2005. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-960-8). 218-224 (2005). MSC: 68W05 68P20 68Q25 68W40 PDFBibTeX XMLCite \textit{R. Ostrovsky} and \textit{Y. Rabani}, in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC'05. Baltimore, MD, USA, May 22--24, 2005. New York, NY: Association for Computing Machinery (ACM). 218--224 (2005; Zbl 1192.68835) Full Text: DOI
Naor, Assaf; Rabani, Yuval; Sinclair, Alistair Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. (English) Zbl 1104.68087 J. Funct. Anal. 227, No. 2, 273-303 (2005). MSC: 68R10 05C80 51F99 PDFBibTeX XMLCite \textit{A. Naor} et al., J. Funct. Anal. 227, No. 2, 273--303 (2005; Zbl 1104.68087) Full Text: DOI
Cheriyan, Joseph; Karloff, Howard; Yuval, Rabani Approximating directed multicuts. (English) Zbl 1080.05039 Combinatorica 25, No. 3, 251-269 (2005). Reviewer: Mirko Lepović (Kragujevac) MSC: 05C20 05C85 68W25 90C27 PDFBibTeX XMLCite \textit{J. Cheriyan} et al., Combinatorica 25, No. 3, 251--269 (2005; Zbl 1080.05039) Full Text: DOI
Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair Low distortion maps between point sets. (English) Zbl 1192.68366 Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 272-280, electronic only (2004). MSC: 68Q25 68U05 68U10 68T10 PDFBibTeX XMLCite \textit{C. Kenyon} et al., in: Proceedings of the 36th annual ACM symposium on theory of computing, STOC 2004. Chicago, IL, USA, June 13--15, 2004. New York, NY: ACM Press. 272--280 (2004; Zbl 1192.68366) Full Text: DOI
Calinescu, Gruia; Karloff, Howard; Rabani, Yuval Approximation algorithms for the 0-extension problem. (English) Zbl 1087.68128 SIAM J. Comput. 34, No. 2, 358-372 (2004). MSC: 68W25 90C35 90C59 PDFBibTeX XMLCite \textit{G. Calinescu} et al., SIAM J. Comput. 34, No. 2, 358--372 (2004; Zbl 1087.68128) Full Text: DOI
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval Subquadratic approximation algorithms for clustering problems in high dimensional spaces. (English) Zbl 1089.68119 Mach. Learn. 56, No. 1-3, 153-167 (2004). MSC: 68T10 68R10 68T05 PDFBibTeX XMLCite \textit{A. Borodin} et al., Mach. Learn. 56, No. 1--3, 153--167 (2004; Zbl 1089.68119) Full Text: DOI
Jayram, T. S.; Khot, Subhash; Kumar, Ravi; Rabani, Yuval Cell-probe lower bounds for the partial match problem. (English) Zbl 1084.68037 J. Comput. Syst. Sci. 69, No. 3, 435-447 (2004). MSC: 68P15 68Q17 PDFBibTeX XMLCite \textit{T. S. Jayram} et al., J. Comput. Syst. Sci. 69, No. 3, 435--447 (2004; Zbl 1084.68037) Full Text: DOI
Jayram, T. S.; Khot, Subhash; Kumar, Ravi; Rabani Yuval Cell-probe lower bounds for the partial match problem. (English) Zbl 1192.68215 Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 667-672, electronic only (2003). MSC: 68P15 68Q17 PDFBibTeX XMLCite \textit{T. S. Jayram} et al., in: Proceedings of the thirty-fifth annual ACM symposium on theory of computing, STOC 2003. San Diego, CA, USA. New York, NY: ACM Press. 667--672 (2003; Zbl 1192.68215) Full Text: DOI
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon, Claire; Rabani, Yuval Approximation schemes for clustering problems. (English) Zbl 1192.68894 Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 50-58, electronic only (2003). MSC: 68W25 68U05 PDFBibTeX XMLCite \textit{W. Fernandez de la Vega} et al., in: Proceedings of the thirty-fifth annual ACM symposium on theory of computing, STOC 2003. San Diego, CA, USA. New York, NY: ACM Press. 50--58 (2003; Zbl 1192.68894) Full Text: DOI
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval Lower bounds for high dimensional nearest neighbor search and related problems. (English) Zbl 1104.68442 Aronov, Boris (ed.) et al., Discrete and computational geometry. The Goodman-Pollack Festschrift. Berlin: Springer (ISBN 3-540-00371-1/hbk). Algorithms Comb. 25, 253-274 (2003). MSC: 68P10 68U05 PDFBibTeX XMLCite \textit{A. Borodin} et al., Algorithms Comb. 25, 253--274 (2003; Zbl 1104.68442)
Ostrovsky, Rafail; Rabani, Yuval Polynomial-time approximation schemes for geometric MIN-sum median clustering. (English) Zbl 1323.68574 J. ACM 49, No. 2, 139-156 (2002). MSC: 68W25 68Q17 68U05 PDFBibTeX XMLCite \textit{R. Ostrovsky} and \textit{Y. Rabani}, J. ACM 49, No. 2, 139--156 (2002; Zbl 1323.68574) Full Text: DOI
Calinescu, Gruia; Chakrabarti, Amit; Karloff, Howard; Rabani, Yuval Improved approximation algorithms for resource allocation. (English) Zbl 1049.90035 Cook, William J. (ed.) et al., Integer programming and combinatorial optimization. 9th international IPCO conference, Cambridge, MA, USA, May 27–29, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43676-6). Lect. Notes Comput. Sci. 2337, 401-414 (2002). MSC: 90B80 90C10 90C59 PDFBibTeX XMLCite \textit{G. Calinescu} et al., Lect. Notes Comput. Sci. 2337, 401--414 (2002; Zbl 1049.90035) Full Text: Link
Rabani, Yuval Search and classification of high dimensional data. (English) Zbl 1013.68839 Jansen, Klaus (ed.) et al., Approximation algorithms for combinatorial optimization. 5th international workshop, APPROX 2002, Rome, Italy, September 17-21, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2462, 1-2 (2002). MSC: 68U99 68P10 68W25 PDFBibTeX XMLCite \textit{Y. Rabani}, Lect. Notes Comput. Sci. 2462, 1--2 (2002; Zbl 1013.68839) Full Text: Link
Barkol, Omer; Rabani, Yuval Tighter lower bounds for nearest neighbor search and related problems in the cell probe model. (English) Zbl 1015.68057 J. Comput. Syst. Sci. 64, No. 4, 873-896 (2002). MSC: 68P10 PDFBibTeX XMLCite \textit{O. Barkol} and \textit{Y. Rabani}, J. Comput. Syst. Sci. 64, No. 4, 873--896 (2002; Zbl 1015.68057) Full Text: DOI
Moss, Anna; Rabani, Yuval Approximation algorithms for constrained node weighted Steiner tree problems. (English) Zbl 1323.68573 Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 373-382 (2001). MSC: 68W25 05C05 05C85 68Q17 90C35 90C59 PDFBibTeX XMLCite \textit{A. Moss} and \textit{Y. Rabani}, in: Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6--8, 2001. New York, NY: ACM Press. 373--382 (2001; Zbl 1323.68573) Full Text: DOI
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval Stability preserving transformations: Packet routing networks with edge capacities and speeds. (English) Zbl 1027.90006 Kosaraju, Deborah, Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms. Washington, DC, USA, January 7-9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. 601-610 (2001). MSC: 90B10 68M10 PDFBibTeX XMLCite \textit{A. Borodin} et al., in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, Washington, DC, USA, January 7--9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; New York, NY: ACM, Association for Computing Machinery. 601--610 (2001; Zbl 1027.90006)
Naor, Joseph; Rabani, Yuval Tree packing and approximating \(k\)-cuts. (English) Zbl 0987.05089 Kosaraju, Deborah, Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms. Washington, DC, USA, January 7-9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. 26-27 (2001). MSC: 05C85 90C35 05C70 05C05 PDFBibTeX XMLCite \textit{J. Naor} and \textit{Y. Rabani}, in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, Washington, DC, USA, January 7--9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; New York, NY: ACM, Association for Computing Machinery. 26--27 (2001; Zbl 0987.05089)
Calinescu, Gruia; Karloff, Howard; Rabani, Yuval Approximation algorithms for the 0-extension problem. (English) Zbl 0987.05086 Kosaraju, Deborah, Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms. Washington, DC, USA, January 7-9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. 8-16 (2001). MSC: 05C85 90C35 05C12 PDFBibTeX XMLCite \textit{G. Calinescu} et al., in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, Washington, DC, USA, January 7--9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; New York, NY: ACM, Association for Computing Machinery. 8--16 (2001; Zbl 0987.05086)
Kleinberg, Jon; Rabani, Yuval; Tardos, Éva Fairness in routing and load balancing. (English) Zbl 0996.68021 J. Comput. Syst. Sci. 63, No. 1, 2-20 (2001). MSC: 68M10 PDFBibTeX XMLCite \textit{J. Kleinberg} et al., J. Comput. Syst. Sci. 63, No. 1, 2--20 (2001; Zbl 0996.68021) Full Text: DOI
Barkol, Omer; Rabani, Yuval Tighter bounds for nearest neighbor search and related problems in the cell probe model. (English) Zbl 1296.68174 Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 388-396 (2000). MSC: 68U05 68Q17 PDFBibTeX XMLCite \textit{O. Barkol} and \textit{Y. Rabani}, in: Proceedings of the thirty-second annual ACM symposium on theory of computing, STOC 2000. Portland, Oregon, USA, May 21--23, 2000. New York, NY: ACM Press. 388--396 (2000; Zbl 1296.68174) Full Text: DOI
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael A decomposition theorem for task systems and bounds for randomized server problems. (English) Zbl 0977.68039 SIAM J. Comput. 30, No. 5, 1624-1661 (2000). MSC: 68Q17 68W20 91A46 68Q25 PDFBibTeX XMLCite \textit{A. Blum} et al., SIAM J. Comput. 30, No. 5, 1624--1661 (2000; Zbl 0977.68039) Full Text: DOI
Kushilevitz, Eyal; Ostrovsky, Rafail; Rabani, Yuval Efficient search for approximate nearest neighbor in high dimensional spaces. (English) Zbl 0963.68078 SIAM J. Comput. 30, No. 2, 457-474 (2000). MSC: 68Q25 68P05 PDFBibTeX XMLCite \textit{E. Kushilevitz} et al., SIAM J. Comput. 30, No. 2, 457--474 (2000; Zbl 0963.68078) Full Text: DOI
Kleinberg, Jon; Rabani, Yuval; Tardos, Éva Allocating bandwidth for bursty connections. (English) Zbl 0979.05098 SIAM J. Comput. 30, No. 1, 191-217 (2000). MSC: 05C85 68R10 PDFBibTeX XMLCite \textit{J. Kleinberg} et al., SIAM J. Comput. 30, No. 1, 191--217 (2000; Zbl 0979.05098) Full Text: DOI
Călinescu, Gruia; Karloff, Howard; Rabani, Yuval An improved approximation algorithm of MULTIWAY CUT. (English) Zbl 0986.90043 J. Comput. Syst. Sci. 60, No. 3, 564-574 (2000). MSC: 90C27 90C05 68R10 68W25 PDFBibTeX XMLCite \textit{G. Călinescu} et al., J. Comput. Syst. Sci. 60, No. 3, 564--574 (2000; Zbl 0986.90043) Full Text: DOI
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval Subquadratic approximation algorithms for clustering problems in high dimensional spaces. (English) Zbl 1345.62088 Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 435-444 (1999). MSC: 62H30 68W25 PDFBibTeX XMLCite \textit{A. Borodin} et al., in: Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1--4, 1999. New York, NY: ACM, Association for Computing Machinery. 435--444 (1999; Zbl 1345.62088) Full Text: DOI
Borodin, Allan; Ostrovsky, Rafail; Rabani, Yuval Lower bounds for high dimensional nearest neighbor search and related problems. (English) Zbl 1346.68077 Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 312-321 (1999). MSC: 68P10 68Q17 PDFBibTeX XMLCite \textit{A. Borodin} et al., in: Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1--4, 1999. New York, NY: ACM, Association for Computing Machinery. 312--321 (1999; Zbl 1346.68077) Full Text: DOI
Kleinberg, Jon; Rabani, Yuval; Tardos, Éva Allocating bandwidth for bursty connections. (English) Zbl 0963.68019 STOC ’97. Proceedings of the 29th annual ACM symposium on theory of computing, El Paso, TX, USA, May 4-6, 1997. New York, NY: ACM, Association for Computing Machinery, 664-673 (1999). MSC: 68M20 PDFBibTeX XMLCite \textit{J. Kleinberg} et al., in: Proceedings of the 29th annual ACM symposium on theory of computing, STOC '97. El Paso, TX, USA, May 4--6, 1997. New York, NY: ACM, Association for Computing Machinery. 664--673 (1999; Zbl 0963.68019)
Ostrovsky, Rafail; Rabani, Yuval Universal \(O(\text{congestion}+ \text{dilation}+ \log^{1+\varepsilon} N)\) local control packet switching algorithms. (English) Zbl 1072.68514 STOC ’97. Proceedings of the 29th annual ACM symposium on theory of computing, El Paso, TX, USA, May 4–6, 1997. New York, NY: ACM, Association for Computing Machinery. 644-653 (1999). MSC: 68M20 PDFBibTeX XMLCite \textit{R. Ostrovsky} and \textit{Y. Rabani}, in: Proceedings of the 29th annual ACM symposium on theory of computing, STOC '97. El Paso, TX, USA, May 4--6, 1997. New York, NY: ACM, Association for Computing Machinery. 644--653 (1999; Zbl 1072.68514)
Kushilevitz, Eyal; Ostrovsky, Rafail; Rabani, Yuval Efficient search for approximate nearest neighbor in high dimensional spaces. (English) Zbl 1029.68542 STOC ’98. Proceedings of the 30th annual ACM symposium on theory of computing, Dallas, TX, USA, May 23-26, 1998. New York, NY: ACM, Association for Computing Machinery. 614-623 (1998). MSC: 68P10 PDFBibTeX XMLCite \textit{E. Kushilevitz} et al., in: Proceedings of the 30th annual ACM symposium on theory of computing, STOC '98. Dallas, TX, USA, May 23--26, 1998. New York, NY: ACM, Association for Computing Machinery. 614--623 (1998; Zbl 1029.68542)
Călinescu, Gruia; Karloff, Howard; Rabani, Yuval An improved approximation algorithm for MULTIWAY CUT. (English) Zbl 1028.68220 STOC ’98. Proceedings of the 30th annual ACM symposium on theory of computing, Dallas, TX, USA, May 23-26, 1998. New York, NY: ACM, Association for Computing Machinery, 48-52 (1998). MSC: 68W25 90C27 68R10 PDFBibTeX XMLCite \textit{G. Călinescu} et al., in: Proceedings of the 30th annual ACM symposium on theory of computing, STOC '98. Dallas, TX, USA, May 23--26, 1998. New York, NY: ACM, Association for Computing Machinery. 48--52 (1998; Zbl 1028.68220)
Rabani, Yuval; Rabinovich, Yuri; Sinclair, Alistair A computational view of population genetics. (English) Zbl 0955.92023 Random Struct. Algorithms 12, No. 4, 313-334 (1998). MSC: 92D10 37N25 PDFBibTeX XMLCite \textit{Y. Rabani} et al., Random Struct. Algorithms 12, No. 4, 313--334 (1998; Zbl 0955.92023) Full Text: DOI
Ajtai, Miklos; Aspnes, James; Naor, Moni; Rabani, Yuval; Schulman, Leonard J.; Waarts, Orli Fairness in scheduling. (English) Zbl 0917.68017 J. Algorithms 29, No. 2, 306-357 (1998). MSC: 68M20 PDFBibTeX XMLCite \textit{M. Ajtai} et al., J. Algorithms 29, No. 2, 306--357 (1998; Zbl 0917.68017) Full Text: DOI
Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing. (English) Zbl 0936.68116 J. Algorithms 27, No. 2, 218-235 (1998). MSC: 68W05 PDFBibTeX XMLCite \textit{C. Kenyon} et al., J. Algorithms 27, No. 2, 218--235 (1998; Zbl 0936.68116) Full Text: DOI Link
Fiat, Amos; Foster, Dean P.; Karloff, Howard; Rabani, Yuval; Ravid, Yiftach Competitive algorithms for layered graph traversal. (English) Zbl 0915.68056 SIAM J. Comput. 28, No. 2, 447-462 (1998). MSC: 68Q10 68Q25 PDFBibTeX XMLCite \textit{A. Fiat} et al., SIAM J. Comput. 28, No. 2, 447--462 (1998; Zbl 0915.68056) Full Text: DOI
Aumann, Yonatan; Rabani, Yuval An \(O(\log k)\) approximate min-cut max-flow theorem and approximation algorithm. (English) Zbl 0910.05038 SIAM J. Comput. 27, No. 1, 291-301 (1998). Reviewer: E.Ederle (München) MSC: 05C38 68R10 90B10 PDFBibTeX XMLCite \textit{Y. Aumann} and \textit{Y. Rabani}, SIAM J. Comput. 27, No. 1, 291--301 (1998; Zbl 0910.05038) Full Text: DOI
Irani, Sandy; Rabani, Yuval On the value of coordination in distributed decision making. (English) Zbl 0856.68076 SIAM J. Comput. 25, No. 3, 498-519 (1996). MSC: 68W15 68Q25 PDFBibTeX XMLCite \textit{S. Irani} and \textit{Y. Rabani}, SIAM J. Comput. 25, No. 3, 498--519 (1996; Zbl 0856.68076) Full Text: DOI
Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing. (Preliminary version). (English) Zbl 0853.68092 Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, held in Atlanta, GA, USA, January 28-30, 1996. Philadelphia, PA: SIAM. 351-358 (1996). MSC: 68Q10 PDFBibTeX XMLCite \textit{C. Kenyon} et al., in: Proceedings of the 7th annual ACM-SIAM symposium on discrete algorithms, SODA '96, held in Atlanta, GA, USA, January 28--30, 1996. Philadelphia, PA: SIAM. 351--358 (1996; Zbl 0853.68092)
Rabani, Yuval; Tardos, Éva Distributed packet switching in arbitrary networks. (English) Zbl 0936.68010 Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22-24, 1996. New York, NY: ACM, 366-375 (1996). MSC: 68M10 68M20 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{É. Tardos}, in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 366--375 (1996; Zbl 0936.68010)
Aumann, Yonatan; Rabani, Yuval Improved bounds for all optical routing. (English) Zbl 0960.68514 Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA: SIAM. 567-576 (1995). MSC: 68M10 68Q25 PDFBibTeX XMLCite \textit{Y. Aumann} and \textit{Y. Rabani}, in: Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, SODA '95, San Francisco, CA, USA, January 22--24, 1995. Philadelphia, PA: SIAM; New York, NY: ACM. 567--576 (1995; Zbl 0960.68514)
Ajtai, Miklos; Aspnes, James; Naor, Moni; Rabani, Yuval; Schulman, Leonard J.; Waarts, Orli Fairness in scheduling. (English) Zbl 0851.90060 Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA: SIAM. 477-485 (1995). MSC: 90B35 PDFBibTeX XMLCite \textit{M. Ajtai} et al., in: Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, SODA '95, San Francisco, CA, USA, January 22--24, 1995. Philadelphia, PA: SIAM; New York, NY: ACM. 477--485 (1995; Zbl 0851.90060)
Bartal, Yair; Fiat, Amos; Rabani, Yuval Competitive algorithms for distributed data management. (English) Zbl 1294.68071 J. Comput. Syst. Sci. 51, No. 3, 341-358 (1995). MSC: 68P15 05C85 68R10 68W15 PDFBibTeX XMLCite \textit{Y. Bartal} et al., J. Comput. Syst. Sci. 51, No. 3, 341--358 (1995; Zbl 1294.68071) Full Text: DOI Link
Rabani, Yuval; Rabinovich, Yuri; Sinclair, Alistair A computational view of population genetics (preliminary version). (English) Zbl 0920.92015 Proceedings of the 27th annual ACM symposium on the theory of computing (STOC). Las Vegas, NV, USA, May 29 - June 1, 1995. New York, NY: ACM, 83-92 (1995). MSC: 92D10 92-08 PDFBibTeX XMLCite \textit{Y. Rabani} et al., in: Proceedings of the 27th annual ACM symposium on the theory of computing, STOC '95. Las Vegas, NV, USA, May 29 -- June 1, 1995. New York, NY: ACM. 83--92 (1995; Zbl 0920.92015)
Arora, Sanjeev; Rabani, Yuval; Vazirani, Umesh Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). (English) Zbl 1345.68150 Proceedings of the 26th annual ACM symposium on theory of computing, STOC ’94, Montreal, Canada, May 23–25, 1994. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-663-8). 459-467 (1994). MSC: 68Q17 60J20 68Q25 68Q87 68T20 PDFBibTeX XMLCite \textit{S. Arora} et al., in: Proceedings of the 26th annual ACM symposium on theory of computing, STOC '94, Montreal, Canada, May 23--25, 1994. New York, NY: Association for Computing Machinery (ACM). 459--467 (1994; Zbl 1345.68150) Full Text: DOI
Fiat, Amos; Rabani, Yuval; Ravid, Yiftach Competitive \(k\)-server algorithms. (English) Zbl 0806.68056 J. Comput. Syst. Sci. 48, No. 3, 410-428 (1994). MSC: 68Q25 68P10 PDFBibTeX XMLCite \textit{A. Fiat} et al., J. Comput. Syst. Sci. 48, No. 3, 410--428 (1994; Zbl 0806.68056) Full Text: DOI
Fiat, A.; Rabani, Y.; Ravid, Y.; Schieber, B. A deterministic \(O(k^ 3)\)-competitive \(k\)-server algorithm for the circle. (English) Zbl 0806.68052 Algorithmica 11, No. 6, 572-578 (1994). MSC: 68W15 68Q25 PDFBibTeX XMLCite \textit{A. Fiat} et al., Algorithmica 11, No. 6, 572--578 (1994; Zbl 0806.68052) Full Text: DOI
Bartal, Yair; Karloff, Howard; Rabani, Yuval A better lower bound for on-line scheduling. (English) Zbl 0807.68013 Inf. Process. Lett. 50, No. 3, 113-116 (1994). MSC: 68M20 90B35 PDFBibTeX XMLCite \textit{Y. Bartal} et al., Inf. Process. Lett. 50, No. 3, 113--116 (1994; Zbl 0807.68013) Full Text: DOI
Karloff, Howard; Rabani, Yuval; Ravid, Yiftach Lower bounds for randomized \(k\)-server and motion-planning algorithms. (English) Zbl 0804.68066 SIAM J. Comput. 23, No. 2, 293-312 (1994). MSC: 68Q25 93C85 PDFBibTeX XMLCite \textit{H. Karloff} et al., SIAM J. Comput. 23, No. 2, 293--312 (1994; Zbl 0804.68066) Full Text: DOI
Rabani, Yuval; Galil, Zvi On the space complexity of some algorithms for sequence comparison. (English) Zbl 0745.68060 Theor. Comput. Sci. 95, No. 2, 231-244 (1992). MSC: 68Q25 68W10 PDFBibTeX XMLCite \textit{Y. Rabani} and \textit{Z. Galil}, Theor. Comput. Sci. 95, No. 2, 231--244 (1992; Zbl 0745.68060) Full Text: DOI
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael A decomposition theorem and bounds for randomized server problems. (English) Zbl 0977.68543 33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24-27, 1992. Washington, DC: IEEE Computer Society Press, 197-207 (1992). MSC: 68Q25 93C85 PDFBibTeX XMLCite \textit{A. Blum} et al., in: 33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24--27, 1992. Washington, DC: IEEE Computer Society Press. 197--207 (1992; Zbl 0977.68543)