MSE Research Project Database

Instance models for covering and clustering problems

Project Leader: Anthony Wirth
Collaborators: James Saunderson (Monash)
Primary Contact: Tony Wirth (
Keywords: optimisation
Disciplines: Computing and Information Systems
Domains: Optimisation of resources and infrastructure

Covering and clustering are two classical computational tasks. The first seeks to find coherent communities or groups, in networks say, while the second seeks the smallest family of examples, say, to represent a collection of items. Over the decades, researchers and practitioners have developed a plethora of algorithms and tools for these problems. In addition, there are numerous theoretical results about the performance of algorithms designed for these problems. At times, these two strands of algorithm development have diverged. In an effort to unify theory and practice, we consider special families of problem instances on which certain algorithms perform well. How well do these instances model real-life inputs? Which algorithms perfom better on them, and why is that so? When is greedy the right approach?