Concepedia

Approximation Complexity

Approximation Complexity is a computational complexity measure that characterizes the inherent difficulty of approximating optimal solutions to NP-hard problems within guaranteed performance bounds, distinguishing it from exact complexity by focusing on the trade-off between solution quality and computational tractability.

471

Publications

32.5K

Citations

815

Authors

387

Institutions

Publications per year

2017–2026

62

Parents

Publications

471

A threshold of ln <i>n</i> for approximating set cover

Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text

, , +16

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text

, , +14

Complexity and approximation: Combinatorial optimization problems and their approximability properties

Computers & Mathematics with Applications · 2000 · 1.3K citations

, , +13

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

On the hardness of approximating vertex cover

Irit Dinur, Samuel Safra · Annals of Mathematics · 2005 · 635 citations · Full text

, , +15

1–5 of 471

Authors

815

  1. SA
    Sanjeev Arora

    Princeton University, United States

    10 publications · 3.2K citations

    10

    h-index

  2. ID
    Irit Dinur

    Weizmann Institute of Science, Israel

    8 publications · 1.2K citations

    8

    h-index

  3. UF
    Uriel Feige

    Weizmann Institute of Science, Israel

    8 publications · 4.3K citations

    8

    h-index

  4. GJ
    Gerhard J. Woeginger

    Graz University of Technology, Austria

    7 publications · 374 citations

    7

    h-index

  5. JN
    Joseph Naor

    Technion – Israel Institute of Technology, Israel

    7 publications · 453 citations

    7

    h-index

1–5 of 815

Institutions

387

  1. University of California, Berkeley

    Berkeley, United States

    22 h-index

    31 publications

    5K citations

  2. Princeton University

    Princeton, United States

    15 h-index

    31 publications

    4.2K citations

  3. Massachusetts Institute of Technology

    Cambridge, United States

    14 h-index

    24 publications

    3.3K citations

  4. Technion – Israel Institute of Technology

    Haifa, Israel

    13 h-index

    17 publications

    1.5K citations

  5. Weizmann Institute of Science

    Rehovot, Israel

    13 h-index

    15 publications

    4.6K citations

  6. Carnegie Mellon University

    Pittsburgh, United States

    13 h-index

    23 publications

    1.7K citations

  7. Cornell University

    Ithaca, United States

    13 h-index

    16 publications

    1.2K citations

  8. Centre National de la Recherche Scientifique

    Paris, France

    11 h-index

    21 publications

    441 citations

1–8 of 387

Venues

  1. SIAM Journal on Computing

    25 publications · 2.3K citations

    21

    h-index

  2. arXiv (Cornell University)

    Repository · 27 publications · 609 citations

    15

    h-index

  3. Theoretical Computer Science

    14 publications · 604 citations

    12

    h-index

  4. Mathematical Programming

    12 publications · 825 citations

    12

    h-index

  5. Journal of the ACM

    JACM · 11 publications · 5.3K citations

    11

    h-index

1–5