×

Found 98 Documents (Results 1–98)

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI arXiv

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).
PDFBibTeX XMLCite
Full Text: Link Link

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
Full Text: DOI

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
Full Text: DOI arXiv Link

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: Link

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).
PDFBibTeX XMLCite
Full Text: DOI Link

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

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).
PDFBibTeX XMLCite

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
Full Text: DOI

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).
PDFBibTeX XMLCite

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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

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).
PDFBibTeX XMLCite
Full Text: DOI

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).
PDFBibTeX XMLCite
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: Link

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).
PDFBibTeX XMLCite
Full Text: DOI

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

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).
PDFBibTeX XMLCite

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

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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

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

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

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

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

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

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

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

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

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).
PDFBibTeX XMLCite
Full Text: DOI

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

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Software