�ݺ�ߣ

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
.
......
On the Parallel Complexity of Minimum Sum
of Diameters Clustering
Nopadon Juneam 1,2 and Sanpawat Kantabutra 2
1Department of Computer Science, Chiang Mai University, Chiang Mai, Thailand
2The Theory of Computation Group, Department of Computer Engineering
Chiang Mai University, Chiang Mai, Thailand
Nopadon Juneam (Chiang Mai University) 114th RGJ Seminar Series April 29, 2016 1 / 19

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Outline
1 Introduction
Minimum Sum of Diameters Clustering Problem
(MSDCP)
2 Basic Parallel Complexity Theory
Basic Concepts
3 Our Contributions
Parallel Complexity
More Practical Parallel Algorithm

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Outline
1 Introduction
(MSDCP)
Basic Concepts
3 Our Contributions
Parallel Complexity

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Background
Conceptually, a cluster is a collection of similar entities, where
entities within the same cluster are more similar to each other than
to those in diﬀerent clusters.
A basic problem of clustering is to partition a given ﬁnite set of
entities into clusters.
Applications of clustering are known in a variety of areas such as
data mining, machine learning, pattern recognition, bioinformatics
and social networking.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Basic Problem of Clustering
Given a set of points on the plane.
(e.g. climate data such as GPS locations)

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Basic Problem of Clustering (cont.)
The set of points partitioned into three clusters.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Minimum Sum of Diameters Clustering
Problem (MSDCP)
Objective: Partition a given set of entities into clusters such that the sum
of clusters’ diameters is minimized.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Minimum Sum of Diameters Clustering
Problem (MSDCP) (cont.)
“In this work, we studied the complexity of the MSDCP
on a parallel computer.”

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Outline
1 Introduction
(MSDCP)
Basic Concepts
3 Our Contributions
Parallel Complexity

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Key Concepts
Researches in computational complexity theory are centered on the
question how diﬃcult it is to solve a computational problem in the
term of some computational resources.
On a parallel computer, important computational resources are the
computational time and the number of processors.
Problems can obtain some speed improvement while being solved
on a parallel computer. However, a signiﬁcant speed up may not
possible for every problem.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Time Order
source: https://apelbaum.wordpress.com/2011/05/05/big-o/

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Theory of P-Completeness [2]
The parallel complexity class NC contains all the problems that
have a polylogarithmic-time parallel algorithm using a polynomial
number of processors.
Such a parallel algorithm is considered as a highly parallel solution,
or eﬃcient parallel algorithm for the problem.
In contrast, the parallel complexity class P-complete contains all
the problems for which no highly parallel solution is known; up to
some technicality.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Research Question
“Whether the MSDCP is in NC or P-complete? If it is in NC,
then how good its highly parallel solution can be?
in the use of parallel algorithms in practice.”

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Outline
1 Introduction
(MSDCP)
Basic Concepts
3 Our Contributions
Parallel Complexity

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Previous Studies
For the case of a partition into three or more clusters
In 1978, Brucker showed that the MSDCP is NP-hard [1]
The problem is extremely diﬃcult.
An exact solution to the problem requires at least exponential time.
For the case of a partition into two clusters
In 1987, Hansen and Jaumard gave an algorithm in O(n3
log n)
time [3].
The problem becomes easy.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Our Contributions
For the case of a partition into two clusters, we show that the
MSDCP is in class NC. That is, the problem has highly parallel
solutions.
1 The problem can be fasteastly solved in O(log n) parallel time
and n6
processors on the Common CRCW PRAM model
of parallel computer.
2 A more practical NC algorithm can be implemented in
O(log3
n) parallel time using n3.376
processors on the EREW
PRAM model of parallel computer.
In addition, these results will be published in [4].

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
References
P. Brucker.
On the complexity of clustering problems.
In R. Henn, B. Korte, and W. Oettli, editors, Optimization and
Operations Research, volume 157 of Lecture Notes in Economics and
Mathematical Systems, pages 45–54. Springer Berlin Heidelberg, 1978.
R. Greenlaw, H. J. Hoover, and W. L. Ruzzo.
Limits to Parallel Computation: P-completeness Theory.
Oxford University Press, Inc., New York, NY, USA, 1995.
P. Hansen and B. Jaumard.
Minimum sum of diameters clustering.
Journal of Classiﬁcation, 4(2):215–226, 1987.
N. Juneam and S. Kantabutra.
On the parallel complexity of minimum sum of diameters clustering.
Journal of Internet Technology, 2017 (in press).

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Acknowledgment
Financial support from the Thailand Research Fund through
the Royal Golden Jubilee Ph.D. Program
(Grant No. PHD/0267/2552) is acknowledged.

.....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
....
.
....
.
.....
.
....
.
.....
.
....
.
....
.
Thanks You
juneam.n@gmail.com

�ݺ�ߣ

On the Parallel Complexity of Minimum Sum of Diameters clustering

Recommended

More Related Content

Similar to On the Parallel Complexity of Minimum Sum of Diameters clustering (20)

Recently uploaded (20)

On the Parallel Complexity of Minimum Sum of Diameters clustering