Apps
Contact
Seminars
RSS FeedDecember 8th, 2012
Project 2 Presentations
Just wrapping up project 2 presentations in the CS 6212 – Algorithms class. Here is a survey that is open to students.
__
August 12th, 2012
Job scheduling mechanisms in Clouds
As more and more organizations have started to use the cloud for their computing needs (I have been using Amazon Web Services, commonly known as the EC2 cloud for more than two years now), a relatively new set of challenges has arisen. The cloud providers provide computing resources, while the organizations care about their analytical and computing jobs being completed, irrespective of the computing resources they require. The organizations would like to place a value on the job, instead of the resource, and there is currently a missing link between the two.
As a regular reviewer for Computing Reviews, I have just finished a formal review for Near-optimal Scheduling Mechanisms for Deadline-Sensitive jobs in Large Computing Clusters, and that work specifically tries to address these new kinds of challenges that we are all observing as the movement to cloud computing gathers further steam.
July 13th, 2012
A graph that requires 5 colors but does not contain K5 (complete graph on 5 vertices)
This was a question in the Design and Analysis of Algorithms (CS 6212) final last night. I don’t know how the students did, but essentially, one way to create such a graph is take a C5 (a cycle on 5 vertices), that we know requires 3 colors. Then, to this, we attach a K2 (a simple 2 node connected graph), and connect the two vertices of K2 to each vertex in C5. 
This graph requires 5 colors (3 for C5 + 2 other ones that cannot overlap with colors used in C5), and this graph does not have a K5, since the original graph (C5) does not have a triangle.
So far so good. Interesting question – What is the graph with fewest number of vertices, such that it is K5 free, and it’s chromatic number is at least 5? I suspect this is the same graph, but I do not have any proof.
January 21st, 2012
Politics and Algorithms rarely mix, but when they do, they involve food stamps and bin packing
[This is one of rare posts, that will be cross-posted to the Guy Down the Street blog as well.]