Network design is a class of problems with wide applicability, including well-known problems such as Steiner tree and the travelling salesperson problem. In general, these problems concern the task of finding subgraphs establishing connections between nodes with some desired property, such as fault tolerance or structural constraints.
One technique that has found success in this area is the use of tree embeddings, which transform the input graph into a tree, where the problem is usually easier to solve.
However, these techniques cannot perfectly embed the graph, and thus incur a loss in the approximation factor of O(log n), even for simple input graphs such as grids, expanders, and bounded-treewidth graphs.
In this talk, we will look at a classic problem in the area of network design, the group Steiner tree problem, as well as the approximation techniques used to solve it.
We will then introduce the setting of bounded treewidth, and see how we can use this additional structure to design a lossless reduction-to-tree technique for network design problems.
Finally, we will see how this technique can be applied to group Steiner tree to break the O(log n) tree embedding barrier and obtain an optimal approximation factor (matching trees), with the running time increasing as a function of the treewidth.
This talk is based on joint work with Parinya Chalermsook, Syamantak Das, Guy Even and Bundit Laekhanukit.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne