Concepedia

Probabilistic Approximation Algorithms

Probabilistic Approximation Algorithms is an approximation algorithm that belongs to the class of randomized algorithms, distinguished by its use of randomness in the computational process to achieve an approximate solution with provable performance guarantees in expectation or with high probability.

237

Publications

21.1K

Citations

466

Authors

268

Institutions

Publications per year

2017–2026

37

Parents

Publications

237

Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Nathan Halko, Per‐Gunnar Martinsson, Joel A. Tropp · SIAM Review · 2011 · 4.1K citations

, , +16

Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms

Jonathan S. Yedidia, William T. Freeman, Yaakov Weiss · IEEE Transactions on Information Theory · 2005 · 1.7K citations

, , +13

Generalized Belief Propagation

Jonathan S. Yedidia, William T. Freeman, Yair Weiss · 2000 · 916 citations

, , +15

Approximating the Permanent

Mark Jerrum, Alistair Sinclair · SIAM Journal on Computing · 1989 · 793 citations

, , +16

Approximating probabilistic inference in Bayesian belief networks is NP-hard

Paul Dagum, Michael Luby · Artificial Intelligence · 1993 · 773 citations

, , +16

1–5 of 237

Authors

466

  1. PM
    Per‐Gunnar Martinsson

    University of Colorado Boulder, United States

    6 publications · 4.5K citations

    6

    h-index

  2. JA
    Joel A. Tropp

    California Institute of Technology, United States

    5 publications · 4.5K citations

    5

    h-index

  3. EM
    Enrique Miranda

    Universidad de Oviedo, Spain

    4 publications · 95 citations

    4

    h-index

  4. RD
    Rina Dechter

    University of California, Irvine, United States

    4 publications · 154 citations

    4

    h-index

  5. ML
    Michael Luby

    International Computer Science Institute, United States

    3 publications · 1.1K citations

    3

    h-index

1–5 of 466

Institutions

268

  1. Stanford University

    Stanford, United States

    10 h-index

    18 publications

    2.3K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    5 h-index

    6 publications

    2.6K citations

  3. University of California, Berkeley

    Berkeley, United States

    5 h-index

    6 publications

    1.1K citations

  4. University of California, Irvine

    Irvine, United States

    5 h-index

    9 publications

    286 citations

  5. University of Oxford

    Oxford, United Kingdom

    5 h-index

    7 publications

    337 citations

  6. Cornell University

    Ithaca, United States

    5 h-index

    6 publications

    316 citations

  7. Microsoft (United States)

    Redmond, United States

    4 h-index

    6 publications

    247 citations

  8. Carnegie Mellon University

    Pittsburgh, United States

    4 h-index

    8 publications

    623 citations

1–8 of 268

Venues

  1. arXiv (Cornell University)

    Repository · 15 publications · 490 citations

    12

    h-index

  2. Journal of Approximation Theory

    6 publications · 225 citations

    6

    h-index

  3. Journal of Complexity

    4 publications · 71 citations

    4

    h-index

  4. SIAM Journal on Computing

    4 publications · 1.1K citations

    4

    h-index

  5. International Journal of Approximate Reasoning

    4 publications · 653 citations

    4

    h-index

1–5