tag:blogger.com,1999:blog-53632813911465946252017-06-24T19:03:56.697-07:00Theory ChatJagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-5363281391146594625.post-2454037573576548732011-10-26T06:51:00.000-07:002011-10-26T06:54:22.649-07:00Lower bound for element distinctness problem<div dir="ltr" style="text-align: left;" trbidi="on"><br /><i><b>Summary</b>: We discuss the method of proving lower bounds on a linear decision tree model using connected components argument. A lower bound of Ω(</i><i>n log</i><i>n) for element distinctness problem(EDP) follows from this argument. </i><br /> <br /><br />We are given an input <i>X=(x1,x2,..,x_n)</i> and a property P; the problem is to decide if <i>X</i> has property P. In EDP, we are interested in knowing if all x_is are distinct.<br /><b><br /></b><br /><b>What is a connected component?</b><br /><b><br /></b><br />Every input point belongs to R^n. Hence, the entire input space R^n can be partioned into `Yes' and `No' regions; a point from `Yes' region has property P while a point from `No' region does not.<br /><br />In EDP, problem suppose <i>n</i>=2, so the input space is R^2. The input space has two regions: Yes and No. Points that lie in <i>x1<x2</i> and <i>x1>x2</i> form the `Yes' region and points on the line <i>x1=x2</i> form the `No' region.<br /><br />Two points<i> a</i> and <i>b</i> are said to be connected if they both belong to `Yes'(No) region and there exists a continuous path from <i>a</i> to <i>b </i>that passes only through `Yes'(No) region.<b> </b>For example, all points in <i>x1<x2</i> region are connected. But a point <i>a</i> in <i>x1<x2</i> and <i>b</i> in <i>x1>x2</i> are not connected since any path from <i>a</i> to <i>b</i> must pass through the line <i>x1=x2</i> which is a `No' region.<br /><br /><br /><b>Computational Model</b> <br /><br />The model of computation here is a linear decision tree, which takes as input X and outputs `Yes' or `No' depending on whether X satisfies the given property P or not. For EDP, the decision tree outputs `Yes` if all the elements are distinct and `No' otherwise. Each internal node <i>v</i> of the tree contains a linear function in input variables d_v(X) and three edges: >0, <0 and =0. Given an input vector X, we decide to take the branch corresponding to the value of d_v(X). Computation starts at the root node and control branches recursively to its children. The decision is made when control reaches a leaf. Each leaf node is labelled `Yes' or `No'. We can think of the decision tree as a function <i>F </i>: R<sup>n</sup> → {Yes,No} .<br /><br />Linear decision trees have the following geometric interpretation: Each internal node defines a hyperplane with equation d(X). We branch at a node depending on whether the input is above, below or on the hyperplane. Let l be a leaf node. Consider the set of all input points R(l) that reach the leaf node l. The set R(l) contains all the points which satisfy the inequalities or equalities along its root-to-leaf path. Since such a set is formed by intersection of half-planes, the resulting set must be a convex region. A convex region is always connected. Hence, a single leaf node can accommodate only one connected component.<br /><br /><i>Claim 1</i>.<i> If two points </i>a<i> and </i>b<i> reach a leaf then any point that is a convex combination of </i>a<i> and </i>b<i> must also reach the same leaf.</i><br /><br /><b>Bound on the height of the tree</b><br /><br />The number of leaves is at least the number of connected components in $F^{-1}(Yes)$ and $F^{-1}(No)$. It follows that the height of the linear decision tree must be at least $\log_{3}( F^{-1}(Yes) + F^{-1}(No) )$, implying a lower bound on the number of comparisons the linear decision tree must make in order to give the correct answer.<br /><br /><br /><br /><b>Number of connected components in EDP problem </b><br /><br />All that we have to do is get a lower bound of the number of connected components.<br /><br /><i>Claim 2. There are n! 'Yes' connected components in R^n.</i><br /><br />Take a point <i>a</i> in R^n with all distinct coordinates and let <i>b</i> be a non-identical permutation of coordinates of <i>a</i>.<i> </i>For example, if <i>a</i>=(1,4,5) then <i>b</i> can be (4,5,1) in R^3. Since <i>b </i>is a non-identical permutation of <i>a</i>, there must be an inversion pair (i,j). i.e there must be two coordinates i and j such that <i>a_i > a_j</i> and <i>b_i < b_j</i> or vice versa. Can inputs <i>a</i> and <i>b</i> reach the same leaf? This is not possible since the straight line connecting <i>a</i> and <i>b</i> must pass through some point with <i>x_i=x_j</i>. So there exists a convex combination of <i>a</i> and <i>b</i> which belongs to 'No' region(which contradicts Claim 1). Every non-identical permutation of <i>a</i> is in a connected component of its own, hence there are <i>n! </i>connected components.<br /><br /><i>Claim 3. The height of the decision tree must be at least log(n!) = </i><i>Ω(</i><i>n log</i><i> n). </i><br /><br /><br /><br /><b>Takeaway Puzzle</b>: Prove an <i>Ω(</i><i>n log</i><i> n) </i>lower bound for the following problem by reducing from EDP: Given an array of numbers is there a contiguous subsequence whose sum is zero?<br /><br /></div>Jagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-51204568739526516972011-10-14T21:28:00.000-07:002011-10-14T21:28:07.398-07:00Theory Chat: k-server, Metrical Task Systems & Metrical Service...<a href="http://theorychatclub.blogspot.com/2011/09/k-server-metrical-task-systems-and.html?spref=bl">Theory Chat: k-server, Metrical Task Systems & Metrical Service...</a>: [@ 2:30pm. 15 Sept 2011. SIC-305 KReSIT] <div><br /></div><div>In this talk I introduced the three problems mentioned in the title and the connection between them. I mentioned a few lower / upper bounds. I later introduced the problem I am working on - metrical service systems with k servers. I presented a proof of a lower bound on the competitive ratio, which holds for any metric space with sufficiently many points. For the case when the underlying metric space is uniform (and the problem is in some sense a variant of the caching problem), I presented a deterministic algorithm (proposed by Prof. Sundar) with competitive ratio k times the lower bound. Improving on this upper bound is one of the problems I am stuck with.</div><div><br /></div><div>The proof of the competitive ratio used a result called the skew Bollobás theorem, which I would like to talk on some time. The proof uses what is called the "wedge product" of vectors, in addition to elementary linear algebra. In another talk, I would like to present a randomized algorithm for MSS with k servers on uniform metric space, as well as a few online traversal problem, and their "equivalence" with one another and with MSS.</div><div><br /></div><div>Ashish Chiplunkar</div>Ashish Chiplunkarhttp://www.blogger.com/profile/11182987978496475494noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-23451788736404345192011-10-04T08:04:00.000-07:002011-10-19T03:45:14.719-07:00Wish List<div dir="ltr" style="text-align: left;" trbidi="on"><div dir="ltr" style="text-align: left;" trbidi="on"><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Topics I would like to learn about:</b></div><div style="text-align: left;"></div><ol style="text-align: left;"><li>Multiplicative weights update method.[<a href="http://www.cs.princeton.edu/%7Earora/pubs/MWsurvey.pdf">link</a>]</li><li>Semi-definite programming.</li><li>Natural Proofs--<i>I know nothing about this, but sounds interesting.</i></li><li>What are the common ways of exploiting planarity in design of algorithms?</li><li>Derandomization/Random walks/Expanders.</li></ol><div style="text-align: left;"><br /></div><div style="text-align: left;"><b>Topics I would like to give talks on:</b></div><ol style="text-align: left;"><a href="http://latex.codecogs.com/gif.latex?x_1,%20%5Ccdots,x_n" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><br /></a><li>Lower bounds for Element distinctness Problem.<br />Consider the following problem: Given an array of <i>n</i> elements <i>x<sub>1</sub>,..,x<sub>n</sub></i> decide if <i>x<sub>i</sub>=x<sub>j</sub></i> for some <i>i≠j</i>. Prove that any comparison-based algorithm takes at least Ω(<i>n</i>log<i>n</i>) operations to decide if all the elements are distinct.</li><li>Trade-off revealing LPs</li><li>Lower bounds for Linear Satisfiability. An Ω(<i>n<sup>r/2</sup></i>) lower bound for the following problem: For some fixed linear equation in <i style="background-color: white; text-align: justify;">r</i><span class="Apple-style-span" style=";color:white;" > variables, given a set of </span><i style="background-color: white; text-align: justify;">n</i><span class="Apple-style-span" style=";color:white;" > real numbers, do any </span><i style="background-color: white; text-align: justify;">r</i><span class="Apple-style-span" style=";color:white;" > of them satisfy the equation? </span> [ <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.6626">pdf</a> ]</li><li>Broadcast scheduling on paths. <i>A problem I was initially working on..there is a small gap in bounds and I would like to solicit ideas for improvement.</i></li><li>Farkas Lemma and its applications.</li><li>Introduction to Matroids.</li></ol><i><i></i></i><br /><div style="text-align: left;"><i><i><br /></i></i></div><i><i></i></i><br /><div style="text-align: left;">--Jagadish<br /><br /><br /><br /><div><b>Topics I would like to see presented:</b></div><div></div><ol><li>"A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by Daniele Micciancio and Panagiotis Voulgaris, a breakthrough result on the shortest vector problem. [ pdf ]</li><li>Proof(s) of the Borsuk Ulam theorem, a generalization of Brouwer's fixed point theorem to arbitrary dimensions.[ <a href="http://www.math.neu.edu/%7Eking_chris/Borsuk-Ulam.pdf">pdf</a> ] Another excellent source is the book by Matousek, titled "Using the Borsuk-Ulam theorem".</li><li>An intro to entropy and information theory<i>.</i></li><li>Szemeredi's regularity lemma and applications.</li></ol><div>Note: I am willing to discuss on the Micciancio-Voulgaris paper.<br /><br /></div><div><b>Topics I would like to present:</b></div><ol><a href="http://latex.codecogs.com/gif.latex?x_1,%20%5Ccdots,x_n" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><br /></a><li>Expanders.</li><li>Linear algebraic methods in combinatorics.</li><li>The Guth-Katz bound on the Erdős distance problem: Terrence Tao has a nice expository <a href="ttp://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/">post</a>. <i>This is a complex proof and I could use some help</i>.</li><li>Extractors and derandomization.</li></ol>--Aravind<br /><div><br /><b><br /><br />Topics I would like to see presented:<br /></b><ol><li>Interior point methods to solve convex optimization problems</li><li>UGC, hardness of approximation<br /></li><li>SDPs</li><li>Expanders</li><li>PCP theorem :D<br /></li></ol><b>Topics I would like to present:<br /></b><ol><li>Two player games and Lemke-Howson algorithm</li><li>PPAD problems and properties<br /></li><li>Lemke's algorithm<br /></li></ol><br /></div></div>-Ruta.<br /><div style="text-align: left;"><i><i><br /></i></i></div><i><i></i></i></div><i><i></i></i></div>Jagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.com3tag:blogger.com,1999:blog-5363281391146594625.post-70447393955895253712011-10-03T10:18:00.000-07:002011-10-28T06:24:57.006-07:00Short & Clever Results<div dir="ltr" style="text-align: left;" trbidi="on"><ol style="text-align: left;"><li>Katona's proof of Erdos-Ka-Rado theorem. [<a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem">link</a>]</li><li>Karger's randomized min-cut algorithm.[<a href="http://www.cs.cmu.edu/%7Eavrim/Randalgs97/lect0122">Notes</a>]</li><li>Interactive Proof System.</li><li>Deffie-Hellman protocol.[<a href="http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange">link</a>]</li><li>Dobkin and Lipton's lower bound proof of element distinctness problem.</li><li>Reflections on trust by Ken Thompson.[<a href="http://www.google.co.in/url?sa=t&source=web&cd=2&ved=0CCUQFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.167.4096%26rep%3Drep1%26type%3Dpdf&rct=j&q=reflections%20on%20trust&ei=deeJTv-2FMLtrQe41vHFDA&usg=AFQjCNEO0WV7WIElePwP0JYiiOcKCgZLkA&sig2=XO0SvQ9gUa9_YpT_HLzraQ&cad=rja">pdf</a>]</li><li>Schöning's Algorithm for 3SAT.[<a href="http://www.google.co.in/url?sa=t&source=web&cd=1&ved=0CBsQFjAA&url=http%3A%2F%2Fwww.eecs.berkeley.edu%2F%7Eluca%2Fcs174%2Fnotes%2Fnote9.ps&rct=j&q=schoning%20algorithm%20for%203%20sat&ei=o-mJTtDLNcnKrAe7-ZTODA&usg=AFQjCNFRrE_F9iRE-WOZPHiGkU9_UGVimA&sig2=xjXvwVGE0cHlDopphYX3ig&cad=rja">pdf</a>]</li><li>Perceptron algorithm for finding a separating plane.</li><li>Deradomization using an expander.(<a href="http://www.cs.huji.ac.il/%7Enati/PAPERS/diskrete_mathematik_06.pdf">Linial's ppt</a>)</li><li>Least Common Ancestor in O(1) time. (<a href="http://www.google.co.in/url?sa=t&source=web&cd=1&sqi=2&ved=0CBsQFjAA&url=http%3A%2F%2Fcourses.csail.mit.edu%2F6.897%2Fspring05%2Flec%2Flec15.pdf&rct=j&q=Least%20Common%20Ancestor%20in%20O%281%29%20time%20erik%20demaine&ei=7OeJTqHKIc7qrQeF0LHhDA&usg=AFQjCNGdI4T8ek_k8QdByE1NulZJJ_3EdQ&sig2=YXdSP_OOPiZFF6fM5pv76g&cad=rja">Erik Demaine notes</a>). </li></ol><br /></div>Jagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-87449327603947281842011-09-19T00:32:00.000-07:002011-09-19T01:01:02.579-07:00Internship at IBM IRL<div dir="ltr" style="text-align: left;" trbidi="on"><br />I did internship at IBM IRL Bangalore from 12-May-2011 to 05-Aug-2011 under <a href="http://www.almaden.ibm.com/cs/people/jayram/">Jayram T.S.</a> who is the head of the algorithms department of IBM Almaden lab and is currently visting Bangalore.<br /><br />I came to know about the internship from our revered senior Sreyash Kenkre. It seems that every year IBM sends pamphlets to Universities (including US universities) inviting students for internship. Even IIT Bombay got the invitation. I saw the notice on the KR Building Office notice board. But I agreed to go for internship only when Sreyash rebuked me. The process was simple. I sent my Resume to Jayram & Vinayak Pandit of IRL. They took an telephonic interview (when IND-PAK semifinal was going on). Mainly they talked about the project and then I talked about my work. After around 2 weeks they sent me an offer.<br /><br />The work was totally new for me and was not related to my Thesis. They wanted to explore about the possible way of solving a problem on linear algebra using different techniques. For that I needed to do some coding. Mainly I needed to solve a large number of LPs using Matlab/C++. But the main part was to explain the observations using theory. For that we needed to go through some papers on unique solutions of LPs / Counting the faces of polytopes etc. Finally we realized that the problem is related to the field of <a href="http://dsp.rice.edu/cs">compressed sensing</a>.<br /><br />It was a very nice experience working with Jayram. He is a good teacher. Whenever there were some terms/topics unknown to me in the papers we were reading, he would explain me the basics of them himself instead of asking me to read about them offline. Overall the feeling was that we were learning together intercepted by he teaching me the basics.<br /><br /><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody><tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-nm1BDGDbG5w/TnbzKXLuK7I/AAAAAAAAASU/uknY1GalFCg/s1600/2.jpg" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="265" src="http://4.bp.blogspot.com/-nm1BDGDbG5w/TnbzKXLuK7I/AAAAAAAAASU/uknY1GalFCg/s400/2.jpg" width="400" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">In front of security desk of IRL. More photos <a href="https://www.facebook.com/media/set/?set=a.10150283409127345.372833.621717344">here</a>.</td></tr></tbody></table>Apart from the office work, we also went for two trips in Bangalore and one mentor-intern lunch all sponsored by IBM. They were full of fun. Many of the interns (>50%) were from US universities. So I came to know about their respective schools/professors etc.<br /><br />I think PhD students should go for internships (may be in the summers of 2nd and 3rd year) which will enable them to expand their horizon. Since I had prior work experience, I thought I did not need to go for internship. But now I would like to say that working with research lab is a different experience. In the worst case, it will help us decide about what to do after the PhD. (Most of my co-interns from US had already done internship in the summers of previous years.)<br /><br />Another thing I realized that we (theorychat walas) should discuss more among ourselves about new papers/topics even not directly related to our thesis. For example we can make theory chat to be something like this: <a href="http://www.cs.dartmouth.edu/~theory/winter_2011.html">Dartmouth Theory Reading Group</a></div>Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-13481233444212405652011-09-16T01:27:00.001-07:002011-09-16T20:55:36.443-07:00Internship at GatechI visited Georgia Tech this summer (15th June 2011 to 31st August 2011), to work with Prof. Maria Florina Balcan. I would like to share my experiences during this visit.<br /><br />I met her at a 10 days school on Algorithmic Game Theory in Shanghai last year, where she was one of the speakers. We discussed a few things then. As I wanted to go for an internship this summer, I started applying in Jan. I wrote to 3 Profs, including her, with some time gaps. People generally travel during the summer, so it seems they do not prefer to take summer interns. However, after a while she replied saying that she would be happy to host me. That is how I got it.<br /><br />The experience was good. I got to interact with many post-docs and two more profs. The people are very professional, and result/paper oriented. I think that it is good for phd students. My mentor is very active, up to date about the results, and all enthu to find out new things. But she was also travelling till 1st August. So, we got to work actively only during the last month. The area (learning theory) was totally new to me, so I learnt a lot.<br /><br />Theory group at Georgia Tech is strong, and they work in many diverse areas. Two new good profs have joined in theory recently (Nina and Prasad Raghvendra). The group regularly invites renowned people, either to visit for a short duration (Lovasz is visiting now) or to give a talk. There is an invited talk every once in a week. Also, the students meet every week to discuss and give talks.Rutahttp://www.blogger.com/profile/16719588005705188072noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-58283290570013690022011-09-15T03:57:00.000-07:002011-09-15T03:59:05.472-07:00k-server, Metrical Task Systems & Metrical Service Systems<div dir="ltr" style="text-align: left;" trbidi="on">[@ 2:30pm. 15 Sept 2011. SIC-305 KReSIT]<br />Ashish Chiplunkar<br /><br />TODO<br /><br /></div>Jagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-54654955578745542562010-05-18T03:05:00.000-07:002011-01-20T03:06:12.496-08:00Topics in Automata[@ 3:30pm. 18 May - 1 June, 2010. SIC-305 KReSIT]<br />Abhishek Sankaran<br /><br />I will give an overview of some topics related to logic. I will also discuss the problems that I am looking at.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-24938100233955632482010-05-11T03:04:00.000-07:002011-01-20T03:05:08.624-08:00Sweep surfaces[@ 3:30pm. 11 May 2010. SIC-305, KReSIT]<br />Jinesh Machchhar<br /><br />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.<br /><br />Link to writeup: <a href="http://www.cse.iitb.ac.in/%7Ejineshmac/sweep.pdf">http://www.cse.iitb.ac.in/~jineshmac/sweep.pdf</a>Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-5809360429974569442010-04-29T03:02:00.000-07:002011-01-20T03:29:23.446-08:00On the Intergrality ratio of Assymetric travelling salesman problem[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]<br />Sagar Kale<br /><br /><b>Toy problem:</b> TODO.<br /><br />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.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-68513612348475836212010-04-29T03:01:00.000-07:002011-01-20T03:28:51.461-08:00Approximation algorithm for facility location[@ 3:30pm. 29 April, 2010. SIC 305, KReSIT]<br />Srinivas Karthik<br /><br />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<br /><br /><a href="http://portal.acm.org/ft_gateway.cfm?id=258600&type=pdf&coll=GUIDE&dl=GUIDE&CFID=104510823&CFTOKEN=48504661">Link to paper</a>.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-81017890335169543062010-03-30T02:59:00.000-07:002011-01-20T03:30:58.520-08:00Markov chains and mixing[@ 3:30pm. 30 March, 2010. SIC-305 KReSIT]<br />Ayush<br /><br /><b>Toy problem:</b> 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.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-29657077126692758652010-02-23T02:56:00.000-08:002011-01-20T03:23:53.057-08:00Nash Equilibrium for finite two player games[@ 3:30pm. 23 Feb, 2010. S9, Old CSE, 2nd floor]<br />Ruta Mehta<br /><br /><b>Toy problem:</b> TODO<br /><br />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) (<a href="http://www.stanford.edu/%7Esaberi/lecture4.pdf">http://www.stanford.edu/~saberi/lecture4.pdf</a>). If time permites then I will also talk about the complexity class PPAD related to this algorithm.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-51763554741986768362010-02-16T02:55:00.000-08:002011-01-20T03:22:44.091-08:00Online Interval Graph Coloring[3pm. 16 Feb, 2010. S9, Old CSE, 2nd floor]<br />Soumitra Pal <br /><br /><b>Toy problem:</b> 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. <br /><br />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: <a href="http://people.math.gatech.edu/%7Etrotter/rprob.html">http://people.math.gatech.edu/~trotter/rprob.html</a>.<br /><br />I will discuss the optimal online algorithm and the analysis of 8-competitiveness of First-Fit.Soumitra Palhttps://plus.google.com/112053573113454954775noreply@blogger.com0tag:blogger.com,1999:blog-5363281391146594625.post-82263369271683951182010-02-09T04:19:00.000-08:002011-01-19T04:49:24.749-08:00Online bipartite matching<div>[@ 3pm. 9 Feb, 2010. Old CSE, 2nd floor]<br /></div><div>Jagadish M</div><br /><div><a href="http://3.bp.blogspot.com/_2h0mdB5ai5I/TTbYBg8bIAI/AAAAAAAAAMU/RcX3KyCKbSg/s1600/onlinebipart.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://3.bp.blogspot.com/_2h0mdB5ai5I/TTbYBg8bIAI/AAAAAAAAAMU/RcX3KyCKbSg/s1600/onlinebipart.jpg" /></a>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.</div><div><br /></div><div><b>Toy problem</b>: 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.</div><div><i><br /></i></div><div><i>I'll discuss the <a href="http://www.cc.gatech.edu/~vazirani/adwords.pdf">paper by Aranyak.et al</a> 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.</i></div>Jagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.com0