%0 Book Section %1 Brucker1978 %A Brucker, P. %B Optimization and Operations Research: Proceedings of a Workshop Held at the University of Bonn, October 2--8, 1977 %C Berlin, Heidelberg %D 1978 %E Henn, Rudolf %E Korte, Bernhard %E Oettli, Werner %I Springer Berlin Heidelberg %K clustering kdd kdd17 partition %P 45--54 %R 10.1007/978-3-642-95322-4_5 %T On the Complexity of Clustering Problems %U https://doi.org/10.1007/978-3-642-95322-4_5 %X 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. %@ 978-3-642-95322-4

@inbook{Brucker1978, 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.}, added-at = {2017-11-13T17:24:49.000+0100}, address = {Berlin, Heidelberg}, author = {Brucker, P.}, biburl = {https://www.bibsonomy.org/bibtex/2d3f81fa4a1b1d49a8d0204fbdc02c99f/tomhanika}, booktitle = {Optimization and Operations Research: Proceedings of a Workshop Held at the University of Bonn, October 2--8, 1977}, doi = {10.1007/978-3-642-95322-4_5}, editor = {Henn, Rudolf and Korte, Bernhard and Oettli, Werner}, interhash = {e72237d3c86aed2a2a0daf507bd8c1a8}, intrahash = {d3f81fa4a1b1d49a8d0204fbdc02c99f}, isbn = {978-3-642-95322-4}, keywords = {clustering kdd kdd17 partition}, pages = {45--54}, publisher = {Springer Berlin Heidelberg}, timestamp = {2017-11-13T17:24:49.000+0100}, title = {On the Complexity of Clustering Problems}, url = {https://doi.org/10.1007/978-3-642-95322-4_5}, year = 1978 }