Tata Institute of Fundamental Research
A Fine-Grained Approach for Designing (Time and Space) Efficient Algorithms
STCS Seminar
Speaker:
Rajesh Chitnis (Weizmann Institute of Science
Faculty of Mathematics and Computer Science
234 Herzl St., Rehovot 7610001
Israel)
Organiser:
Kavitha Telikepalli
Date:
Tuesday, 10 Jan 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The classical approach for designing algorithms measures the time complexity only as a measure of the input size. In the 90's, Downey and Fellows proposed a fine-grained approach for NP-hard problems: one or more parameters of the input instance are defined, and we investigate the effect of these parameters on the running time. The goal is to design algorithms that work efficiently if the parameters of the input instance are small, even if the size of the input is large. Formally, a problem is said to be fixed-parameter tractable (FPT) with respect to parameter $k$ if the problem can be solved in time $f(k)$ยท$n^{O(1)}$ where f is a computable function and n is the input size.
In the first part of the talk, I will give a brief overview of FPT algorithms. This active area of research has seen many new developments over the last few years. The standard techniques for designing FPT algorithms on undirected graphs such as bidimensionality, treewidth-based dynamic programming, etc. seem to break down for directed graphs. I will present some of my work which overcomes this barrier, and designs optimal FPT and XP algorithms for cut and connectivity problems on directed graphs.
The second part of the talk will be about some recent work on parameterized streaming algorithms. For the Maximum Matching problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.
| Speaker: | Rajesh Chitnis (Weizmann Institute of Science Faculty of Mathematics and Computer Science 234 Herzl St., Rehovot 7610001 Israel) |
| Organiser: | Kavitha Telikepalli |
| Date: | Tuesday, 10 Jan 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The classical approach for designing algorithms measures the time complexity only as a measure of the input size. In the 90's, Downey and Fellows proposed a fine-grained approach for NP-hard problems: one or more parameters of the input instance are defined, and we investigate the effect of these parameters on the running time. The goal is to design algorithms that work efficiently if the parameters of the input instance are small, even if the size of the input is large. Formally, a problem is said to be fixed-parameter tractable (FPT) with respect to parameter $k$ if the problem can be solved in time $f(k)$ยท$n^{O(1)}$ where f is a computable function and n is the input size.
In the first part of the talk, I will give a brief overview of FPT algorithms. This active area of research has seen many new developments over the last few years. The standard techniques for designing FPT algorithms on undirected graphs such as bidimensionality, treewidth-based dynamic programming, etc. seem to break down for directed graphs. I will present some of my work which overcomes this barrier, and designs optimal FPT and XP algorithms for cut and connectivity problems on directed graphs.
The second part of the talk will be about some recent work on parameterized streaming algorithms. For the Maximum Matching problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.
In the first part of the talk, I will give a brief overview of FPT algorithms. This active area of research has seen many new developments over the last few years. The standard techniques for designing FPT algorithms on undirected graphs such as bidimensionality, treewidth-based dynamic programming, etc. seem to break down for directed graphs. I will present some of my work which overcomes this barrier, and designs optimal FPT and XP algorithms for cut and connectivity problems on directed graphs.
The second part of the talk will be about some recent work on parameterized streaming algorithms. For the Maximum Matching problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.