We give an introduction to Approximation Algorithms. The objective here is to design and analyse efficient algorithms that may not be optimum, but is very close to the optimum solution. The challenge is to design algorithms that give solutions which are close to the optimum, without knowing the optimum solution. We will discuss the approximation algorithms for vertex cover probelm, metric traveling sales man problem and the knapsack problem.

Download Presentation Slides (July 12)

Download Presentation Slides (July 13)

Exact exponential algorithms deals with designing “good” exponential time algorithms for computational problems. It is believed that there exists some problems that cannot be solved in polynomial time. However, every combinatorial problem can be solved in exponential time using brute-force search. It is interesting to see if we can design an algorithm whose running time is better than those of the brute-force algorithm. For example, the Travelling Salesman Problem can be solved in time O(n!) time by using brute force. But can we design an algorithm that solves the Travelling Salesman Problem in O(cⁿ) where c is a constant?
In this talk, we will discuss a few techniques for designing efficient Exact exponential algorithms.

Download Presentation Slides

Parameterised algorithms were introduced as a paradigm to cope with NP-hardness. Here the running time of the algorithm is measured not only as a function of the input size but also in terms of a parameter - a property of the input instance or solution. Moreover, the running time can be exponential in parameter but only polynomial in the input size. Thus a parameterised algorithm is efficient when the parameter is very small compared to the input size. In this talk, we will discuss known parameterised algorithms for some problems.

Download Presentation Slides

In online algorithms, we consider optimization problems where the input is received in an online manner (i.e., the input does not arrive as a single batch but as a sequence of input portions) and the output must be produced online (i.e., the algorithm must take immediate and irrevocable decisions in response to each incoming portion taking into account that the future input is not known at any point in time). Online algorithms are ubiquitous in computer science and optimization: from ad-allocation to taxy-dispatching, from network routing to machine learning. In this introductory session, we will study some basic problems, techniques, and models related to online algorithms.

Download Presentation Slides

Matching problems with preferences arise in real life in a variety of applications. In this talk we will introduce the stable matching problem and a natural variant of the problem where participants are allowed to express ties in preferences. With this flexibility, computing the largest stable matching turns out to be NP-Hard. We present a simple and elegant algorithm by Kirlay which gives a constant factor approximation to the problem of computing stable matchings in the presence of ties.
In the second part, we introduce a different notion of optimality namely popularity. A matching is popular if no majority of participants wants to deviate from it. We will present an algorithm to compute a popular matching in the stable marriage problem.

Download Presentation Slides

In a static algorithm, the input given to the algorithm does not change. However, in the dynamic algorithm, the input changes at each time step. For example, in a dynamic graph, at each update step, an edge may be added or removed from the graph. In such a dynamic graph, we want to maintain a property of the graph, say connectivity, matching, shortest path etc. We can always recompute these properties from scratch after each time step, but can we do better? Thus, the aim of the dynamic algorithm is to maintain a property of the graph after each time step. Also, the time taken to process an update should be much less than the time taken to compute the property from scratch. In this talk, I will introduce some simple algorithms for some basic dynamic problems like connectivity, matching, shortest paths etc.

Download Presentation Slides