Concepedia

Fully Polynomial-time Approximation Scheme

A Fully Polynomial-Time Approximation Scheme is an approximation algorithm for an optimization problem that, for any input size and any positive error tolerance ε, delivers a solution within a factor of (1 + ε) of the optimal value and runs in time polynomial in both the problem size and 1/ε.

258

Publications

14K

Citations

441

Authors

254

Institutions

Publications per year

2017–2026

48

Parents

Publications

258

Approximating the Permanent

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

, , +16

Settling the complexity of computing two-player Nash equilibria

Xi Chen, Xiaotie Deng, Shang‐Hua Teng · Journal of the ACM · 2009 · 579 citations

, , +17

Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing

Hironori Kasahara, Narita · IEEE Transactions on Computers · 1984 · 453 citations

, , +17

The maximum concurrent flow problem

Farhad Shahrokhi, David W. Matula · Journal of the ACM · 1990 · 437 citations · Full text

, , +17

Characterizing achievable rates in multi-hop wireless networks

Murali Kodialam, Thyaga Nandagopal · 2003 · 324 citations

, , +16

1–5 of 258

Authors

441

  1. MJ
    Mark Jerrum

    University of Edinburgh, United Kingdom

    11 publications · 1.6K citations

    11

    h-index

  2. PL
    Pinyan Lu

    Microsoft Research Asia (China), China

    11 publications · 238 citations

    10

    h-index

  3. TC
    T.C.E. Cheng

    Hong Kong Polytechnic University, Hong Kong SAR China

    8 publications · 230 citations

    8

    h-index

  4. NH
    Nir Halman

    Hebrew University of Jerusalem, Israel

    8 publications · 271 citations

    8

    h-index

  5. HK
    Hans Kellerer

    University of Graz, Austria

    7 publications · 384 citations

    7

    h-index

1–5 of 441

Institutions

254

  1. Hong Kong Polytechnic University

    Hong Kong, Hong Kong

    12 h-index

    18 publications

    601 citations

  2. Arizona State University

    Tempe, United States

    11 h-index

    29 publications

    1.9K citations

  3. Hebrew University of Jerusalem

    Jerusalem, Israel

    9 h-index

    10 publications

    418 citations

  4. Massachusetts Institute of Technology

    Cambridge, United States

    9 h-index

    23 publications

    960 citations

  5. University of Graz

    Graz, Austria

    8 h-index

    11 publications

    848 citations

  6. University of California, Berkeley

    Berkeley, United States

    8 h-index

    11 publications

    429 citations

  7. University of Edinburgh

    Edinburgh, United Kingdom

    8 h-index

    9 publications

    2.1K citations

  8. Microsoft (United States)

    Redmond, United States

    7 h-index

    7 publications

    292 citations

1–8 of 254

Venues

  1. SIAM Journal on Computing

    16 publications · 1.4K citations

    13

    h-index

  2. Operations Research

    12 publications · 1.1K citations

    12

    h-index

  3. Mathematics of Operations Research

    11 publications · 984 citations

    11

    h-index

  4. Naval Research Logistics (NRL)

    9 publications · 275 citations

    9

    h-index

  5. arXiv (Cornell University)

    Repository · 8 publications · 152 citations

    8

    h-index

1–5