[@ 3:30pm. 18 May - 1 June, 2010. SIC-305 KReSIT]
Abhishek Sankaran
I will give an overview of some topics related to logic. I will also discuss the problems that I am looking at.
Tuesday, May 18, 2010
Tuesday, May 11, 2010
Sweep surfaces
[@ 3:30pm. 11 May 2010. SIC-305, KReSIT]
Jinesh Machchhar
Sweeping is a powerful and versatile method for de fining surfaces. It involves moving an n-dimensional manifold along a 1-dimensional manifold and computing the surface traced out during the above operation. We will refer to the 1-dimensional manifold along which the sweep occurs as the trajectory. In this talk we will consider sweeping a 1-dimensional manifold along a given trajectory.
Link to writeup: http://www.cse.iitb.ac.in/~jineshmac/sweep.pdf
Jinesh Machchhar
Sweeping is a powerful and versatile method for de fining surfaces. It involves moving an n-dimensional manifold along a 1-dimensional manifold and computing the surface traced out during the above operation. We will refer to the 1-dimensional manifold along which the sweep occurs as the trajectory. In this talk we will consider sweeping a 1-dimensional manifold along a given trajectory.
Link to writeup: http://www.cse.iitb.ac.in/~jineshmac/sweep.pdf
Thursday, April 29, 2010
On the Intergrality ratio of Assymetric travelling salesman problem
[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]
Sagar Kale
Toy problem: TODO.
We( Moses Charikar , Michel X. Goemans , Howard Karloff) improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.
Sagar Kale
Toy problem: TODO.
We( Moses Charikar , Michel X. Goemans , Howard Karloff) improve the lower bound on the integrality ratio of the Held-Karp bound for asymmetric TSP with triangle inequality from 4/3 to 2.
Approximation algorithm for facility location
[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]
Srinivas Karthik
The first approximation algorithm with a constant performance guarantee for the (metric) uncapacitated facility problem was given by Shmoys, Tardos, & Aardal. Their algorithm is an LP rounding algorithm with performance guarantee equal to 3/(1 - e^{-3}) = 3.16
Link to paper.
Srinivas Karthik
The first approximation algorithm with a constant performance guarantee for the (metric) uncapacitated facility problem was given by Shmoys, Tardos, & Aardal. Their algorithm is an LP rounding algorithm with performance guarantee equal to 3/(1 - e^{-3}) = 3.16
Link to paper.
Tuesday, March 30, 2010
Markov chains and mixing
[@ 3:30pm. 30 March, 2010. SIC-305 KReSIT]
Ayush
Toy problem: A website has n questions. If you're shown one random question per click, prove that it takes O(n log n) clicks on avg to see all the questions.
Ayush
Toy problem: A website has n questions. If you're shown one random question per click, prove that it takes O(n log n) clicks on avg to see all the questions.
Tuesday, February 23, 2010
Nash Equilibrium for finite two player games
[@ 3:30pm. 23 Feb, 2010. S9, Old CSE, 2nd floor]
Ruta Mehta
Toy problem: TODO
I will be talking about finite two player games, what Nash equilibrium mean for these games, and an algorithm to find a Nash equilibrium (Lemke-Howson) (http://www.stanford.edu/~saberi/lecture4.pdf). If time permites then I will also talk about the complexity class PPAD related to this algorithm.
Ruta Mehta
Toy problem: TODO
I will be talking about finite two player games, what Nash equilibrium mean for these games, and an algorithm to find a Nash equilibrium (Lemke-Howson) (http://www.stanford.edu/~saberi/lecture4.pdf). If time permites then I will also talk about the complexity class PPAD related to this algorithm.
Tuesday, February 16, 2010
Online Interval Graph Coloring
[3pm. 16 Feb, 2010. S9, Old CSE, 2nd floor]
Soumitra Pal
Toy problem: You have a set of jobs j1,..jn each of which has a start time and end time. Each jobs needs to be run on a machine during the specified time interval. What are the minimum number of machines one would require to complete all the jobs? Give a greedy algorithm to solve this problem.
What happens if the intervals are known one by one and you have to take decision about the job immediately? Does your greedy solution work here? It seems that it does not work (Can you work out one counter example?). The problem seems to be solved because there is an optimal online algorithm (no algorithm can be better than that). But people have spent a lot of time on the First-Fit greedy algorithm whose performance analysis is still not closed yet. The performance of an online algorithm is expressed as how worse compared to an optimal offline algorithm (this ratio is called as competitive ratio). So far it is shown that First-Fit is 8-competitive. But it is conjectured that it is 5-competitive. Refer this link for some history: http://people.math.gatech.edu/~trotter/rprob.html.
I will discuss the optimal online algorithm and the analysis of 8-competitiveness of First-Fit.
Soumitra Pal
Toy problem: You have a set of jobs j1,..jn each of which has a start time and end time. Each jobs needs to be run on a machine during the specified time interval. What are the minimum number of machines one would require to complete all the jobs? Give a greedy algorithm to solve this problem.
What happens if the intervals are known one by one and you have to take decision about the job immediately? Does your greedy solution work here? It seems that it does not work (Can you work out one counter example?). The problem seems to be solved because there is an optimal online algorithm (no algorithm can be better than that). But people have spent a lot of time on the First-Fit greedy algorithm whose performance analysis is still not closed yet. The performance of an online algorithm is expressed as how worse compared to an optimal offline algorithm (this ratio is called as competitive ratio). So far it is shown that First-Fit is 8-competitive. But it is conjectured that it is 5-competitive. Refer this link for some history: http://people.math.gatech.edu/~trotter/rprob.html.
I will discuss the optimal online algorithm and the analysis of 8-competitiveness of First-Fit.
Tuesday, February 9, 2010
Online bipartite matching
[@ 3pm. 9 Feb, 2010. Old CSE, 2nd floor]
Jagadish M
The input to the problem is a bipartite graph G=(U,V,E), in which vertices in U arrive in on-line fashion. As each vertex u from U arrives, the edges incident on it are revealed. We need to match u to one of the previously unmatched vertices in V. If no such vertex in V exists, then u remains unmatched. The choice of a match, after it is made, is irrevocable. The objective is to maximize the size of matching resulting after the last vertex arrives.Toy problem: Let us consider the obvious approach: when u arrives assign it to a some unmatched neighbor. Prove that this strategy will give us a matching that is at least half as good as the optimum.
I'll discuss the paper by Aranyak.et al where they consider the generalized version of the problem; the case where a vertex from V can be matched to multiple vertices from U. They have some cool techniques.
Subscribe to:
Posts (Atom)