Helsinki Algorithms Seminar: "Dynamic Programs meet Linear Programs: Approximation Algorithms for Group Steiner Problems on Low-Treewidth Graphs" Parinya Chalermsook
Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design
Map © OpenStreetMap. Some rights reserved.
Parinya Chalermsook
Aalto University
Dynamic Programs meet Linear Programs: Approximation Algorithms for Group Steiner Problems on Low-Treewidth Graphs
Abstract:
Many graph problems can be solved in polynomial time in low-treewidth graphs (e.g. steiner trees, independent set, and vertex cover) and these results rely on dynamic programs (DP) together with the fact that the problem is polynomial-time solvable on low-treewidth graphs. However, for problems that are NP-hard even on trees or graphs of constant treewidth (such as group steiner network problems), DP techniques become inapplicable.
In a series of papers (starting from SODA 2017 paper), we develop a new approach for approximating graph problems that are NP-hard even for constant treewidth. Our technique first constructs a DP table which is NP-hard to optimize. We then solve the DP optimizing problem via linear programming relaxation and dependent randomized rounding. We use this approach to show improved algorithms for many group steiner problems.
This is joint work with Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz.
**
Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.
Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.
Welcome!