Concepedia

Approximation In Parallel Computation

Approximation in Parallel Computation is a theoretical framework in parallel complexity theory that characterizes the efficiency and accuracy of parallel algorithms designed to compute near-optimal solutions for problems where exact solutions are computationally infeasible under polylogarithmic time and polynomial processor constraints.

63

Publications

2.5K

Citations

125

Authors

79

Institutions

Publications per year

2017–2026

15

Parents

Publications

63

Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time

Richard Cole, Uzi Vishkin · SIAM Journal on Computing · 1988 · 186 citations

, , +15

Approximating elementary functions with symmetric bipartite tables

Michael Schulte, James E. Stine · IEEE Transactions on Computers · 1999 · 172 citations

, , +12

Approximating total flow time on parallel machines

Stefano Leonardi, Danny Raz · 1997 · 148 citations

, , +12

Towards a theory of nearly constant time parallel algorithms

J. Gil, Yossi Matias, Uzi Vishkin · 2002 · 146 citations

, , +15

Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values

Omer Berkman, Baruch Schieber, Uzi Vishkin · Journal of Algorithms · 1993 · 140 citations

, , +14

1–5 of 63

Authors

125

  1. UV
    Uzi Vishkin

    University of Maryland, College Park, United States

    4 publications · 489 citations

    4

    h-index

  2. EB
    Eric Balkanski

    Harvard University Press, United States

    3 publications · 63 citations

    3

    h-index

  3. YS
    Yaron Singer

    Harvard University Press, United States

    3 publications · 63 citations

    3

    h-index

  4. RJ
    Rahul Jain

    National University of Singapore, Singapore

    3 publications · 83 citations

    3

    h-index

  5. LP
    Lorant Porkolab

    Max Planck Institute for Informatics, Germany

    3 publications · 199 citations

    3

    h-index

1–5 of 125

Institutions

79

  1. Tel Aviv University

    Tel Aviv, Israel

    6 h-index

    11 publications

    1.1K citations

  2. National University of Singapore

    Singapore, Singapore

    4 h-index

    6 publications

    137 citations

  3. ETH Zurich

    Zurich, Switzerland

    4 h-index

    5 publications

    158 citations

  4. University of Waterloo

    Waterloo, Canada

    3 h-index

    3 publications

    71 citations

  5. Stanford University

    Stanford, United States

    3 h-index

    3 publications

    57 citations

  6. Max Planck Institute for Informatics

    Saarbrücken, Germany

    3 h-index

    5 publications

    125 citations

  7. Carnegie Mellon University

    Pittsburgh, United States

    2 h-index

    3 publications

    49 citations

  8. University of Maryland, College Park

    College Park, United States

    2 h-index

    3 publications

    309 citations

1–8 of 79

Venues

  1. arXiv (Cornell University)

    Repository · 6 publications · 106 citations

    6

    h-index

  2. Journal of Parallel and Distributed Computing

    2 publications · 48 citations

    2

    h-index

  3. SIAM Journal on Computing

    2 publications · 267 citations

    2

    h-index

  4. IEEE Transactions on Parallel and Distributed Systems

    TPDS · 2 publications · 55 citations

    2

    h-index

  5. Journal of Algorithms

    2 publications · 156 citations

    2

    h-index

1–5