Abstract
The class of discrete optimization problems may be partitioned into two subclasses PS and P?. PS is the subclass of problems which are known to be polynomial solvable. P? is the subclass of problems for which it is not yet known whether an algorithm exists which is polynomial bounded. The subclass P? contains the class NPC of NP-complete discrete optimization problems. NPC has the important property that if only one member of NPC can be shown to be polynomial solvable all members of NPC as well as a large number of other combinatorial problems are polynomial solvable. However, it seems to be very unlikely that all NP-complete problems are polynomial solvable.
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
Aho, A. V., Hopcroft, J. E., and J. D. Ullman: The Design and Analysis of Computer Algorithms, Addison Wesley, Reading, Mass., 1974.
Bock, H. H. : Automatische Klassifikation, Vandenhoek & Ruprecht, Göttingen, 1974.
Garey, M. R., Johnson, D. S. and L. Stockmeyer: Some Simplified NP--complete Graph Problems, Theor. Computer Science 1 (1976), 237–267.
Karp, R. M.: Reducibility among Combinatorial Problems, pp., 85–103 in: Miller, R. E. and J. W. Thatcher eds., Complexity of Computer Computations, Plenum Press, New York, 1972.
Stockmeyer, L. : Planar 3-colorability is Polynomial Complete, ACM Sigact News 5, 3 (1973), 19–25.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1978 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brucker, P. (1978). On the Complexity of Clustering Problems. In: Henn, R., Korte, B., Oettli, W. (eds) Optimization and Operations Research. Lecture Notes in Economics and Mathematical Systems, vol 157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-95322-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-95322-4_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08842-4
Online ISBN: 978-3-642-95322-4
eBook Packages: Springer Book Archive