A fundamental class of combinatorial optimization problems involve packing and covering. Examples include maximum independent set, dominating set, set cover, hitting set, etc. Motivated by applications in sensor networks and robotics, natural instances of such problems arise in geometric situations, such as covering points with a small number of disks, viewing “art galleries” with a small number of guards or with a mobile guard on a short route, packing disks or other shapes within a bounded domain, etc. Almost all of these problems are NP-hard even in simple two-dimensional settings. The problems get even harder when we take into account uncertain data, time constraints for scheduled coverage, and routing/connectivity problems in combination with coverage constraints. We discuss several of these geometric optimization problems from the perspective of approximation algorithms and we describe some techniques that have led to new or improved bounds or running times for selected packing, covering, and routing/coverage problems.

Symmetry is a fundamental concept in mathematics, the sciences, and beyond. Understanding symme tries is often crucial for understanding structures. In computer science, we are mainly interes ted in the symmetries of combinatorial structures. Computing the symmetries of such a structure is essentially the same as deciding whether two structures are the same (“isomorphic”). Algori thmically, this is a difficult task that has received a lot of attention since the early days o f computing. It is a major open problem in theoretical computer science to determine the precis e computational complexity of this “Graph Isomorphism Problem”.

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemic al information systems. Today, applications of isomorphism testing and symmetry detection are u biquitous in computing. Prominent examples appear in optimisation, malware detection, and machi ne learning. However, in many of these applications, we only need to decide if two structures a re sufficiently similar, rather than exactly the same. It turns out that determining how simila r two structures are is an even harder computational problem than deciding whether they are iso morphic.

My talk will be an introduction to algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic “Graph Isomorphism Problem” to applications in optimisati on and machine learning.