Direkt zum InhaltDirekt zur SucheDirekt zur Navigation
▼ Zielgruppen ▼

Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Seminar talk Adam Paszke

Wann 28.02.2019 ab 11:15 (Europe/Berlin / UTC100) iCal
Wo Rudower Chaussee 25, Haus 3, R. 408
Kontaktname

You are cordially invited to a seminar talk given by Adam Paszke on Thursday, February 28 at 11:15 at Humboldt-Universität zu Berlin, Rudower Chausse 25, room 3.408.

Title: Weighted domination on classes of bounded expansion

Abstract:

Bounded expansion classes have been shown to admit many ways to approximate the dominating set problem (and its distance-r version), including mutual bounds with 2r-independence numbers. On the other hand, no results for weighted versions of those problems have been obtained until recently.

From the other side, there exists a rich line of over 20 years of research into those problems considering graphs arising mostly from geometrical graph instances only (most notably unit disk graphs). Those approaches, while allowing classes normally considered as “dense”, usually heavily depend on the topology of the underlying space, and thus are hard to lift into a purely combinatorial setting of bounded expansion.

In this talk I will showcase a solution to constant approximation of minimum-weight r-dominating set on bounded expansion classes, via a reduction to weighted set cover. The covering inputs will come from a restricted class of instances that allows to break the O(log |U|) inapproximability bounds which hold in general. The presentation is aimed at a non-specialist audience, and will only assume basic graph theory knowledge, without any expertise in bounded expansion classes.