×

Found 104 Documents (Results 1–100)

Deterministic massively parallel connectivity. (English) Zbl 07774329

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 162-175 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

18th Scandinavian symposium and workshops on algorithm theory, SWAT 2022, Tórshavn, Faroe Islands, June 27–29, 2022. (English) Zbl 1491.68015

LIPIcs – Leibniz International Proceedings in Informatics 227. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik (ISBN 978-3-95977-236-5). x, 33 articles, not consecutively paged, electronic only, open access (2022).
MSC:  68-06 68Wxx 00B25
PDFBibTeX XMLCite
Full Text: DOI Link

Component stability in low-space massively parallel computation. (English) Zbl 07824226

Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 481-491 (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Improved deterministic \((\Delta+1)\) coloring in low-space MPC. (English) Zbl 07824225

Korhonen, Janne H. (ed.), Proceedings of the 40th ACM symposium on principles of distributed computing, PODC ’21, virtual event, Italy, July 26–30, 2021. New York, NY: Association for Computing Machinery (ACM). 469-479 (2021).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Testable properties in general graphs and random order streaming. (English) Zbl 07758318

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 16, 20 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Simple, deterministic, constant-round coloring in the congested clique. (English) Zbl 07323204

Cachin, Christian (ed.) et al., Proceedings of the 39th ACM symposium on principles of distributed computing, PODC ’20, virtual event, August 3–7, 2020. New York, NY: Association for Computing Machinery (ACM). 309-318 (2020).
MSC:  68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph. (English) Zbl 07304204

Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2973-2992 (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Detecting cliques in CONGEST networks. (English) Zbl 1497.68373

Schmid, Ulrich (ed.) et al., 32nd international symposium on distributed computing, DISC 2018, New Orleans, Louisiana, USA, October 15–19, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 121, Article 16, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Deterministic blind radio networks. (English) Zbl 1497.68039

Schmid, Ulrich (ed.) et al., 32nd international symposium on distributed computing, DISC 2018, New Orleans, Louisiana, USA, October 15–19, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 121, Article 15, 17 p. (2018).
MSC:  68M14 68W15 90B18
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online facility location with deletions. (English) Zbl 1522.68760

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 21, 15 p. (2018).
MSC:  68W27 68W40 90B80
PDFBibTeX XMLCite
Full Text: DOI arXiv

Round compression for parallel matching algorithms. (English) Zbl 1427.68354

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 471-484 (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Sublinear graph augmentation for fast query implementation. (English) Zbl 1520.68119

Epstein, Leah (ed.) et al., Approximation and online algorithms. 16th international workshop, WAOA 2018, Helsinki, Finland, August 23–24, 2018. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 11312, 181-203 (2018).
MSC:  68R10 68P05 68W20
PDFBibTeX XMLCite
Full Text: DOI

Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. (English) Zbl 1380.68007

Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). x, 2850 p. (2018).
MSC:  68-06 68Wxx 00B25
PDFBibTeX XMLCite
Full Text: DOI

Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. (English) Zbl 1380.68018

Proceedings of the 2017 ACM symposium on principles of distributed computing, PODC ’17, Washington, DC, USA, July 25–27, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4992-5). 3-12 (2017).
MSC:  68M10 68M14 68W15
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Faster deterministic communication in radio networks. (English) Zbl 1387.68032

Chatzigiannakis, Ioannis (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 (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 139, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Brief announcement: Optimal leader election in multi-hop radio networks. (English) Zbl 1373.68089

Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC ’16, Chicago, IL, USA, July 25–28, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3964-3). 47-49 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Relating two property testing models for bounded degree directed graphs. (English) Zbl 1376.68165

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 1033-1045 (2016).
MSC:  68W20 05C20 05C85
PDFBibTeX XMLCite
Full Text: DOI

Testing cluster structure of graphs. (English) Zbl 1321.68489

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

\((1 + \varepsilon)\)-approximation for facility location in data streams. (English) Zbl 1421.68206

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

An \(O(\log k)\)-competitive algorithm for generalized caching. (English) Zbl 1422.68268

Rabani, Yuval (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). 1681-1689 (2012).
MSC:  68W20 68W27
PDFBibTeX XMLCite
Full Text: Link

Optimal online buffer scheduling for block devices. (English) Zbl 1286.68026

Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 589-598 (2012).
MSC:  68M20 68W27
PDFBibTeX XMLCite
Full Text: DOI

Multiple-choice balanced allocation in (almost) parallel. (English) Zbl 1372.68308

Gupta, Anupam (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 411-422 (2012).
MSC:  68W27 68M20 68W20
PDFBibTeX XMLCite
Full Text: DOI

Planar graphs: random walks and bipartiteness testing. (English) Zbl 1292.68123

Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 423-432 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Almost tight bounds for reordering buffer management. (English) Zbl 1288.68031

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 607-616 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Approximation schemes for capacitated geometric network design. (English) Zbl 1332.68282

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 25-36 (2011).
MSC:  68W25 68M10 68R10
PDFBibTeX XMLCite
Full Text: DOI

Testing monotone continuous distributions on high-dimensional real cubes. (English) Zbl 1288.68248

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). 56-65 (2010).
PDFBibTeX XMLCite

PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k\). (English) Zbl 1273.68404

Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 994-1003 (2009).
MSC:  68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for buy-at-bulk geometric network design. (English) Zbl 1253.68359

Dehne, Frank (ed.) et al., Algorithms and data structures. 11th international symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03366-7/pbk). Lecture Notes in Computer Science 5664, 168-180 (2009).
MSC:  68W25 90C35 90C59
PDFBibTeX XMLCite
Full Text: DOI

Finding a heaviest triangle is not harder than matrix multiplication. (English) Zbl 1302.68123

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 986-994 (2007).
PDFBibTeX XMLCite

On testable properties in bounded degree graphs. (English) Zbl 1302.05184

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 494-501 (2007).
MSC:  05C85 05C75
PDFBibTeX XMLCite

Communication problems in random line-of-sight ad-hoc radio networks. (English) Zbl 1175.68555

Hromkovič, Juraj (ed.) et al., Stochastic algorithms: Foundations and applications. 4th international symposium, SAGA 2007, Zurich, Switzerland, September 13–14, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74870-0/pbk). Lecture Notes in Computer Science 4665, 70-81 (2007).
MSC:  68W20 05C80 90B18
PDFBibTeX XMLCite
Full Text: DOI

Small space representations for metric min-sum \(k\)-clustering and their applications. (English) Zbl 1186.68559

Thomas, Wolfgang (ed.) et al., STACS 2007. 24th annual symposium on theoretical aspects of computer science, Aachen, Germany, February 22–24, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-70917-6/pbk). Lecture Notes in Computer Science 4393, 536-548 (2007).
MSC:  68W25 62H30 68T05
PDFBibTeX XMLCite
Full Text: DOI

Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. (English) Zbl 1162.68817

Brodal, Gerth Stølting (ed.) et al., Algorithms – ESA 2005. 13th annual European symposium, Palma de Mallorca, Spain, October 3–6, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29118-0/pbk). Lecture Notes in Computer Science 3669, 472-483 (2005).
MSC:  68W25 05C85
PDFBibTeX XMLCite
Full Text: DOI

Facility location in sublinear time. (English) Zbl 1084.90027

Caires, Luís (ed.) et al., Automata, languages and programming. 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11–15, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27580-0/pbk). Lecture Notes in Computer Science 3580, 866-877 (2005).
MSC:  90B80 68W20 68W25
PDFBibTeX XMLCite
Full Text: DOI

Computing equilibria for congestion games with (im)perfect information. (English) Zbl 1318.91010

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 746-755 (2004).
MSC:  91A10 68Q25 91A15
PDFBibTeX XMLCite

Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. (English) Zbl 1318.05075

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 496-505 (2004).
PDFBibTeX XMLCite

Estimating the weight of metric minimum spanning trees in sublinear-time. (English) Zbl 1192.68888

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). 175-183, electronic only (2004).
MSC:  68W25 05C05 68W20
PDFBibTeX XMLCite
Full Text: DOI Link

Sublinear-time approximation for clustering via random sampling. (English) Zbl 1098.68113

Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 396-407 (2004).
MSC:  68T10 68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI

Fault-tolerant geometric spanners. (English) Zbl 1374.68654

Proceedings of the 19th annual symposium on computational geometry, SCG/SoCG 2003, San Diego, CA, USA, June 8–10, 2003. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-663-3). 1-10 (2003).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Perfectly balanced allocation. (English) Zbl 1279.68349

Arora, Sanjeev (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 6th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2003 and 7th international workshop on randomization and approximation techniques in computer science, RANDOM 2003, Princeton, NJ, USA, August 24–26, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40770-7/pbk). Lect. Notes Comput. Sci. 2764, 240-251 (2003).
MSC:  68W20 60K30 68M20
PDFBibTeX XMLCite
Full Text: DOI

Improved approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. (English) Zbl 1205.68511

Ibaraki, Toshihide (ed.) et al., Algorithms and computation. 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20695-7/pbk). Lect. Notes Comput. Sci. 2906, 544-553 (2003).
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time approximation schemes for the Euclidean survivable network design problem. (English) Zbl 1057.90053

Widmayer, Peter (ed.) et al., Automata, languages and programming. 29th international colloquium, ICALP 2002, Málaga, Spain, July 8–13, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43864-5). Lect. Notes Comput. Sci. 2380, 973-984 (2002).
PDFBibTeX XMLCite
Full Text: Link

A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract). (English) Zbl 1296.90135

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

Fast approximation schemes for Euclidean multi-connectivity problems. (Extended abstract). (English) Zbl 0973.90528

Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1853, 856-868 (2000).
PDFBibTeX XMLCite

Coloring non-uniform hypergraphs: A new algorithmic approach to the general Lovász local lemma. (English) Zbl 0954.05020

Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 30-39 (2000).
MSC:  05C15 05C65 05C85
PDFBibTeX XMLCite

On approximability of the minimum-cost \(k\)-connected spanning subgraph problem. (English) Zbl 0974.68156

Proceedings of the 10th annual ACM-SIAM symposium on discrete algorithms. Baltimore, MD, USA, January 17-19, 1999. Philadelphia, PA: SIAM. 281-290 (1999).
PDFBibTeX XMLCite

Delayed path coupling and generating random permutations via distributed stochastic processes. (English) Zbl 1118.68581

Proceedings of the 10th annual ACM-SIAM symposium on Discrete algorithms. Baltimore, MD, USA, January 17–19, 1999. Philadelphia, PA: SIAM (ISBN 0-89871-434-6). 271-280 (1999).
MSC:  68R05 68P25 68W10 68W15 65C50 65Y20
PDFBibTeX XMLCite

A polynomial time approximation scheme for Euclidean minimum cost \(k\)-connectivity. (English) Zbl 0913.05069

Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 682-694 (1998).
Reviewer: Jean Pallo (Dijon)
MSC:  05C40 05C85
PDFBibTeX XMLCite

Bounded degree spanning trees (extended abstract). (English) Zbl 1477.68215

Burkard, Rainer (ed.) et al., Algorithms – ESA ’97. 5th annual European symposium, Graz, Austria, September 15–17, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1284, 104-117 (1997).
PDFBibTeX XMLCite
Full Text: DOI

Fast generation of random permutations via networks simulation. (English) Zbl 1379.68335

Diaz, Josep (ed.) et al., Algorithms – ESA ’96. 4th annual European symposium, Barcelona, Spain, September 25–27, 1996. Proceedings. Berlin: Springer (ISBN 3-540-61680-2). Lecture Notes in Computer Science 1136, 246-260 (1996).
MSC:  68W10 68R05 68W40
PDFBibTeX XMLCite
Full Text: DOI

Work-time-optimal parallel algorithms for string problems. (Extended abstract). (English) Zbl 0978.68531

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, 713-722 (1995).
MSC:  68Q25 68P10
PDFBibTeX XMLCite

Parallel and sequential approximation of shortest superstrings. (English) Zbl 1502.68369

Schmidt, Erik M. (ed.) et al., Algorithm theory – SWAT ’94. 4th Scandinavian workshop on algorithm theory, Aarhus, Denmark, July 6–8, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 824, 95-106 (1994).
MSC:  68W25 68W10 68W32
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field