Instance models for covering and clustering problems

Project description

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?

Project team

Leader: Anthony Wirth

Collaborators: James Saunderson (Monash)

Other projects

Optimisation of resources and infrastructure projects


Computing and Information Systems


Optimisation of resources and infrastructure