Concepedia

Inapproximability

Inapproximability is the theoretical property of certain optimization problems that establishes a lower bound on how closely their optimal solution can be approximated in polynomial time, assuming standard complexity-theoretic conjectures such as P ≠ NP.

296

Publications

21.5K

Citations

481

Authors

252

Institutions

Publications per year

2017–2026

39

Parents

Publications

296

Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems

Garth P. McCormick · Mathematical Programming · 1976 · 2.3K citations

, , +10

Towards Sharp Inapproximability For Any 2-CSP

Per Austrin · 2007 · 1.4K citations

, , +17

On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems

E. Amaldi, Viggo Kann · Theoretical Computer Science · 1998 · 764 citations · Full text

, , +15

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel et al. · SIAM Journal on Computing · 2007 · 599 citations · Full text

, , +13

On approximately fair allocations of indivisible goods

R.J. Lipton, Evangelos Markakis, Elchanan Mossel et al. · 2004 · 530 citations

, , +17

1–5 of 296

Authors

481

  1. SK
    Subhash Khot

    Georgia Institute of Technology, United States

    15 publications · 1.8K citations

    14

    h-index

  2. VG
    Venkatesan Guruswami

    Carnegie Mellon University, United States

    12 publications · 610 citations

    11

    h-index

  3. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    11 publications · 353 citations

    10

    h-index

  4. LT
    Luca Trevisan

    University of California, Berkeley, United States

    8 publications · 639 citations

    9

    h-index

  5. OS
    Ola Svensson

    École Polytechnique Fédérale de Lausanne, Switzerland

    7 publications · 388 citations

    7

    h-index

1–5 of 481

Institutions

252

  1. University of California, Berkeley

    Berkeley, United States

    15 h-index

    22 publications

    2.4K citations

  2. Princeton University

    Princeton, United States

    15 h-index

    29 publications

    1.9K citations

  3. Carnegie Mellon University

    Pittsburgh, United States

    15 h-index

    23 publications

    1.8K citations

  4. Georgia Institute of Technology

    Atlanta, United States

    14 h-index

    26 publications

    2.5K citations

  5. KTH Royal Institute of Technology

    Stockholm, Sweden

    13 h-index

    17 publications

    2.5K citations

  6. Stanford University

    Stanford, United States

    12 h-index

    19 publications

    1.2K citations

  7. Massachusetts Institute of Technology

    Cambridge, United States

    12 h-index

    20 publications

    1K citations

  8. Technion – Israel Institute of Technology

    Haifa, Israel

    10 h-index

    11 publications

    880 citations

1–8 of 252

Venues

  1. SIAM Journal on Computing

    22 publications · 2.2K citations

    18

    h-index

  2. arXiv (Cornell University)

    Repository · 16 publications · 400 citations

    13

    h-index

  3. Theoretical Computer Science

    11 publications · 1.5K citations

    11

    h-index

  4. ACM Transactions on Algorithms

    TALG · 11 publications · 616 citations

    10

    h-index

  5. SIAM Journal on Discrete Mathematics

    7 publications · 621 citations

    7

    h-index

1–5