Abstract
To specify the set of tractable (practically solvable) computing problems is one of the few main research tasks of theoretical computer science. Because of this the investigation of the possibility or the impossibility to efficiently compute approximations of hard optimization problems becomes one of the central and most fruitful areas of recent algorithm and complexity theory. The current point of view is that optimization problems are considered to be tractable if there exist polynomial-time randomized approximation algorithms that solve them with a reasonable approximation ratio. If a optimization problem does not admit such a polynomial-time algorithm, then the problem is considered to be not tractable.
The main goal of this paper is to relativize this specication of tractability. The main reason for this attempt is that we consider the requirement for the tractability to be strong because of the denition of the complexity as the “worst-case” complexity. This definition is also related to the approximation ratio of approximation algorithms and then an optimization problem is considered to be intractable because some subset of problem instances is hard. But in the practice we often have the situation that the hard problem instances do not occur. The general idea of this paper is to try to partition the set of all problem instances of a hard optimization problem into a (possibly infinite) spectrum of subclasses according to their polynomial-time approximability. Searching for a method enabling such a fine problem analysis (classification of problem instances) we introduce the concept of stability of approximation. To show that the application of this concept may lead to a “fine” characterization of the hardness of particular problem instances we consider the traveling salesperson problem and the knapsack problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T. Andreae, H.-J. Bandelt: Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Disr. Math. 8 (1995), pp. 1–16.
S. Arora: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 37 th IEEE FOCS, IEEE 1996, pp. 2–11.
S. Arora: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In: Proc. 38 th IEEE FOCS, IEEE 1997, pp. 554–563.
D. P. Bovet, C. Crescenzi: Introduction to the Theory of Complexity, Prentice-Hall, 1993.
M. A. Bender, C. Chekuri: Performance guarantees for the TSP with a parameterized triangle inequality. In: Proc. WADS’99, LNCS, to appear.
.H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger: Towards the Notion of Stability of Approximation Algorithms and the Traveling Salesman Problem. Unpublished manuscript, RWTH Aachen, 1998.
N. Christodes: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsbourgh, 1976.
P. Crescenzi, V. Kann: A compendium of NP optimization problems. http://www.nada.kth.se/theory/compendium/.
S. A. Cook: The complexity of theorem proving procedures. In: Proc 3 rd ACM STOC, ACM 1971, pp. 151–158.
M. R. Garey, D. S. Johnson: Computers and Intractibility. A Guide to the Theory on NP-Completeness. W. H. Freeman and Company, 1979.
K. Gödel:Über formal unentscheidbare Sätze der Principia Mathematica und verwandte Systeme, I. Monatshefte für Mathematik und Physik 38 (1931), pp. 173–198.
J. Håstad: Some optimal inapproximability results. In: Proc. 29th ACM STOC, ACM 1997, pp. 1–10.
D. S. Hochbaum (Ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company 1996.
O. H. Ibarra, C. E. Kim: Fast approximation algorithms for the knapsack and sum of subsets problem. J. of the ACM 22 (1975), pp. 463–468.
D. S. Johnson: Approximation algorithms for combinatorial problems JCSS 9 (1974), pp. 256–278.
R. M. Karp: Reducibility among combinatorial problems. In: R. E. Miller, J.W. Thatcher (Eds.): Complexity of Computer Computations, Plenum Press 1972, pp. 85–103.
L. Lovász: On the ratio of the optimal integral and functional covers. Discrete Mathematics 13 (1975), pp. 383–390.
I. S. B. Mitchell: Guillotine subdivisions approximate polygonal subdivisions: Part II-a simple polynomial-time approximation scheme for geometric k-MST, TSP and related problems. Technical Report, Dept. of Applied Mathematics and Statistics, Stony Brook 1996.
E. W. Mayr, H. J. Prömel, A. Steger (Eds.): Lecture on Proof Verification and Approximation Algorithms. Lecture Notes in Computer Science 1967, Springer 19
Ch. Papadimitriou: The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science 4 (1977), pp. 237–244.
Ch. Papadimitriou: Computational Complexity, Addison-Wesley 1994.
B. A. Trachtenbrot: Algorithms and Automatic Computing Machines. D. C. Heath & Co., Boston, 1963.
I. Wegener: Theoretische Informatik: eine algorithmenorientierte Einführung. B. G. Teubner 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hromkovič, J. (1999). Stability of Approximation Algorithms for Hard Optimization Problems. In: Pavelka, J., Tel, G., Bartošek, M. (eds) SOFSEM’99: Theory and Practice of Informatics. SOFSEM 1999. Lecture Notes in Computer Science, vol 1725. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47849-3_2
Download citation
DOI: https://doi.org/10.1007/3-540-47849-3_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66694-3
Online ISBN: 978-3-540-47849-2
eBook Packages: Springer Book Archive