Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Eleni Mpakali

MSc thesis of Eleni Mpakali

On the meaningful instances of clustering

Supervisor: Dimitris Achlioptas

Clustering is a problem with many different definitions, approaches and applications, but not well defined mathematically. Especially it is not clear how to define meaningfulness, and how to de- termine if a solution is meaningful, in the sense that it reveals some existing inherent in the data structure. When we refer to clustering via optimization of some objective functions, it is usually a task performed efficiently, despite that most existing objective functions are NP-hard. We will present some existing results showing that “meaningful” instances can be solved effi- ciently. In these papers is made apparent (implicitly or explicitly) a connection between structure in the data, and the behavior of the objective function over the space of solutions. We will propose a method exploiting this connection, that could decide for each pair {objective function, dataset}, if it is “meaningful” the particular dataset to be clustered by optimizing (or ap- proximating) this particular objective function.

Defended: Dec. 15, 2014.

Scientific committee


Download thesis.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.