Concepedia

Complexity of approximation algorithms for combinatorial problems

G. V. Gens, E. V. Levner

ACM SIGACT News · 1980 · 48 citations · 13 references

DOI

Concepts

Abstract

In this survey we examine recent results on the complexity of approximation algorithms which have appeared in Russian.

References

13

The complexity of theorem-proving procedures

Stephen Cook · 1971 · 6.2K citations · Full text

, , +17

Approximation algorithms for combinatorial problems

David S. Johnson · Journal of Computer and System Sciences · 1974 · 2.2K citations

, , +12

P-Complete Approximation Problems

Sartaj Sahni, Teofilo F. Gonzalez · Journal of the ACM · 1976 · 1.7K citations · Full text

, , +17

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

Óscar H. Ibarra, Chul E. Kim · Journal of the ACM · 1975 · 959 citations · Full text

, , +11

Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

Gérard Cornuéjols, Marshall L. Fisher, George L. Nemhauser · Management Science · 1977 · 802 citations

, , +17