[Lowerbounds, Upperbounds]

You’re Invited to Celebrate Gary Miller’s 60th Birthday at MillerFest 2006!

April 19-20, 2006
Carnegie Mellon University, Pittsburgh, PA

We are celebrating Gary Miller’s 60th birthday this spring with a banquet and workshop. The banquet will be held Wednesday evening, April 19th, at the Pittsburgh Athletic Association, with the workshop occurring on Carnegie Mellon’s campus the following day. The workshop will feature presentations related to Professor Miller’s research achievements, including computational number theory, randomized algorithms, parallel algorithms, and scientific computing.

For more information, please see the workshop web site:
http://www.aladdin.cs.cmu.edu/workshops/millerfest/

Please register online as soon as possible since this will help us with planning. There is no fee to attend the workshop if you register by Monday, April 3rd. There is small fee to attend the banquet, which promises to be an enjoyable evening featuring reminiscences about the life and career of Professor Miller.

Out-of-town visitors should make their hotel reservations by Wednesday, March 29th, to take advantage of the pre-negotiated workshop rate of \$105 per night (\$119.70 including taxes) at the Holiday Inn near campus. To make your reservations, call the the Holiday Inn (100 Lytton Avenue, Pittsburgh, PA 15213) at 412-682-6200 and be sure to ask for the ALADDIN Workshop rate.

You may also be interested to know that MillerFest is being held in conjunction with CS50, which celebrates fifty years of computer science at Carnegie Mellon. Please see http://www.cs50.cs.cmu.edu/ for a complete schedule of CS50 events.

We look forward to seeing you at MillerFest!

Guy Blelloch, Alan Frieze, and Shanghua Teng

Speaker: Mohit Singh

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs

The minimum spanning tree problem is a fundamental problem in combinatorial optimization. It also has various applications, especially in network design. A favorable property of a connecting network is not only to be ‘cheap’ but also to have ’small load’ on all nodes. A natural way to formulate this problem is via the minimum degree minimum spanning tree (MDMST) problem.

In an instance of the MDMST problem, we are given a graph G=(V,E) and a non-negative cost function c on edges, and the objective is to find a minimum cost spanning tree T under the cost function c such that maximum degree of T is minimized. Here, the maximum degree of T is the maximum degree among all vertices in T.

In this talk, we will present an algorithm for the MDMST problem which returns a MST of maximum degree at most OPT+k where OPT is the minimum maximum degree of any MST and k is the distinct number of costs in any MST of G. We use a lower bound given by a linear programming relaxation to the problem and strengthen known graph-theoretic results on minimum degree subgraphs to prove our result.

This is joint work with R. Ravi.

Several days ago, David asked how to evaluate an adviser and later Lance replied with his post of wisdoms.

David pointed out that he knew of relatively few resources on how to be an adviser. (His post has one link on this.) While I am not ready to write a post of experience like Lance did, I do have a thought to share.

Not long ago, CMU CS alum Scott Berkun gave a talk based on his book on project management. In his talk, Scott told us many interesting stories about his project management experience back in Microsoft. What struck me was his lists of items of “do”s and “don’t”s in management and his list of questions to ask the team members as a project progresses into different stages.

While Scott was focusing on software projects, I believe some of his ideas are applicable to academic advising. For example, he suggests that we should explicitly ask our team members (students) “Do you think you have all the resources you need for you to succeed?” and “Do you feel that this meeting is a waste of your time?” (Whether you get an honest answer back is another matter. And if you don’t expect you can get an honest answer, then you already have a complicated issue to tackle.)

In hindsight, I suppose it’s hardly surprising that academic advisers can draw experiences from software project managers. They are both managing smart people in a creative process. While the two fields have many differences, the human factor can be pretty much the same.

P.S. Scott’s background is in software project management and the book is not directly written for academic advisers. It takes some effort to relate his ideas with advising. So don’t rush out to buy the book and then tell me that you can’t find a short list on how to be an adviser. There isn’t.