Heuristics for NP-hard problems

A while back, Michael was discussing the teaching of heuristics in his undergraduate algorithms class, and had this request:

I wish the standard textbooks would devote a solid chapter on heuristic techniques; in real life, most students are probably more likely to have to implement a heuristic for some NP-hard problem than to have to implement a minimum spanning tree algorithm.

If you remove the word, ’standard’, he may just have got his wish. From the press blurb for the Handbook of Approximation Algorithms and Metaheuristics:

Delineating the tremendous growth in this area, the Handbook of Approximation Algorithms and Metaheuristics covers fundamental, theoretical topics as well as advanced, practical applications. It is the first book to comprehensively study both approximation algorithms and metaheuristics. Starting with basic approaches, the handbook presents the methodologies to design and analyze efficient approximation algorithms for a large class of problems, and to establish inapproximability results for another class of problems. It also discusses local search, neural networks, and metaheuristics, as well as multiobjective problems, sensitivity analysis, and stability.

Browsing the table of contents, the reader encounters an entire section on heuristics, with chapters on local search, stochastic local search, neural networks, genetic algorithms, tabu search, simulated annealing, ant colony optimization and the like. The book is published by CRC, which stands for “Organization-That-Singlehandedly-Destroys-Rain-Forests-While-Making-Your-Biceps-Extremely-Strong”.

I generally have mixed feelings about CRC books: they are good reference texts, but tend to skim over content way too easily, and CRC has this unhealhy obsession with handbooks for everything. But for teaching heuristics, this might be an invaluable reference.

I should mention that the vast majority of the handbook deals with “proper” approximation algorithms, as well as applications to specific areas. The problem is that approximation algorithms is a fast moving field (though maybe not as fast as in the middle 90s), and so a handbook, being a static snapshot of the time, will get dated quickly.

Tenure committee is to Colombian drug cartel as …

Via HWTW, a hilarious advice piece to new profs by Phil Ford at Inside Higher Ed, adapted from a Notorious B.I.G rap, “The Ten Crack Commandments”. The article is great, but the comments are even funnier.

Parallel algorithms: A resurgence ?

My department has a fairly strong systems and hardware group, and some of the buzz I hear about involves the research opportunities in multicore architectures (I’m talking MANY MANY cores, not 2 or 4), and how parallel computation is relevant once again. In fact, I’ve had one request to include basic material on parallel algorithms in my graduate algorithms class.

Juxtaposed with that is the fact that the Stein-enhanced version of Introduction to Algorithms does NOT contain the chapter on parallel algorithms that the old CLR used to have. In fact, I’ll probably use the chapter outline from CLR if I cover parallel algorithms at any level. I wonder what was the thinking behind removing the chapter on parallel methods, and whether this might be reversed in future editions.

Update: (that was quick! – thanks, Cliff): Tom Cormen writes in to explain the decision to remove the chapter on parallel algorithms:

Cliff Stein pointed me to this blog. Suresh asked why we removed the chapter on parallel algorithms when we wrote our second edition.

The chapter on parallel algorithms in the first edition was exclusively on PRAM algorithms. We wrote the second edition mostly during the late 1990s, into early 2001. At the time, PRAM algorithms were yesterday’s news, because the PRAM model was too far from what could be built realistically. We considered including algorithms for some other parallel computing model, but there was no consensus model at the time. We felt that the best decision was to just leave out parallel algorithms and use the pages for other new material.

I’m not surprised. It *was* true that by the time the 2nd ed arrived, PRAMs were yesterday’s news: in fact, streaming and external memory methods were “hotter” at the time. It’ll be interesting to see if multicore actually does spur new interest in parallel algorithms, and not just parallel architectures. In recent months I’ve participated in discussions about algorithm design for things like the Cell and the implied architecture of nVidia’s CUDA, and it’s surprising how often standard parallel algorithms methods like pointer jumping and the like are being reinvented.

What makes the new platforms more interesting is that there are features (especially streaming features) that make the mapping to “standard” PRAM models not so obvious. It may not merely be a mattter of shoehorning new systems into parallel models, but of extending and modifying the models themselves.

SGERs being replaced ?

The new NSF news feeds are great. I get to hear all kinds of interesting tidbits about the NSF, including some recent chatter on encouraging “transformative research”. One direct consequence of this chatter is this (emphasis mine):

[NSF Director] Bement yesterday proposed a three-pronged strategy before the task force on transformative research. It was unanimously adopted by the task force on Tuesday and then unanimously adopted by the Board on Wednesday. Bement’s plan for will:

1. Infuse support of potentially transformative research throughout NSF and all of its programs;

2. Learn how to facilitate potentially transformative research; and

3. Lead the community through opportunities for potentially tranformative research proposal submissions.

[...]

To lead the community, Bement will embark on a three-year trial, during which NSF will replace small grants for exploratory research with a two-tiered “early-concept” award mechanism. Tier I will call for limited funding grants that are internally reviewed. Tier II will entail larger grants requiring additional levels of review. Further, NSF will create a working group to recommend implementation details; a mechanism to monitor and track impact and lessons-learned; and a method to advertise the new approach to the community.

What’s an advanced algorithm ?

And he’s back !!!

After a rather refreshing (if overly hot) vacation in India, I’m back in town, forced to face reality, an impending move, and the beginning of semester. Yep, the summer is drawing to a close, and I haven’t even stuffed my face with hot dogs yet, let alone 59.5 of them (is there something slightly deranged about ESPN covering “competitive eating” as a sport?).

Anyhow, I digress. The burning question of the day is this:

What is an advanced algorithm ?

It might not be your burning question of the day, but it certainly is mine, because I am the proud teacher of the graduate algorithms class this fall.

Some explanation is in order. At most schools, undergrads in CS take some kind of algorithms class, which for the sake of convenience we’ll call the CLRS class (which is not to say that it can’t be a KT class, or a DPV class, or a GT class, or….). At any rate, this is the first substantial algorithms class that the students take, and often it’s the last one.

Now when you get into grad school, you often have to complete some kind of algorithms breadth requirement. In some schools, you can do this via an exam, and in others, you have to take a class. Namely, a graduate algorithms class. Note also that some students taking this class might not have taken an undergrad algorithms class (for example if they were math/physics majors)

What does one teach in such a class ? There are a number of conflicting goals here:

• Advertising: attract new students to work with you via the class. Obviously, you’d like to test them out first a little (this is not the only way of doing this)
• Pedagogy: there’s lots of things that someone might need even if they don’t do algorithms research: topics like approximations and randomization are not usually well covered in an intro algorithms class
• Retaining mindshare: you don’t want to teach graduate algorithms as a CLRS class because you’ll bore all the people who took such a class. On the other hand, you zoom too far ahead, and you lose the people who come to CS from different backgrounds. And the Lord knows we’re desperate nowadays for people to come to CS from different backgrounds (more on this in a later post).

This is obviously not a new problem, and there are numerous models for how to teach a graduate algorithms course, all with their own pros and cons. Some of the extreme points that define the spectrum of solutions are:

• Teach to the top: dive straight into advanced topics; anyone who needs to catch up does so on their own time. This is probably the most appealing solution from a lecturer perspective, because it covers more interesting topics. It’s also most likely to excite the few students who care. Be prepared for bumpy student evals, especially from disgruntled folks who just need a grade so that they can forget all about algorithms for the rest of their Ph.D
• Teach to the bottom: Do a CLRS-redux, with maybe a few advanced topics thrown in at the end (NP-hardness might count as advanced). You’ll bore the good ones, but you’ll bring the entire class along.

A ’split-the-difference’ solution of covering basic material quickly, and then jumping ahead into advanced topics, is also a possibility. Like most solutions of this kind though, it runs the risk of satisfying nobody while trying to satisfy everyone.

All of this elides the most important point though: what constitutes advanced material ? I’ve seen graduate students struggle with NP-hardness, but this is covered in almost any undergraduate algorithms class (or should). What about general technique classes like approximation algorithms and randomization, both of which merit classes in their own right and can only be superficially covered in any algorithms class (the same is true for geometry) ? Advanced data structures can span an entire course, and some of them are quite entertaining. Topics like FFTs, number-theoretic algorithms, (string) pattern matching, and flows also seem to fit into the purview of advanced topics, though they don’t cohere as well with each other.

It seems like an advanced algorithms class (or the advanced portion of a graduate algorithms class) is a strange and ill-defined beast, defined at the mercy of the instructor (i.e ME !). This problem occurs in computational geometry as well; to use graph-theoretic parlance, the tree of topics fans out very quickly after a short path from the root, rather than having a long and well-defined trunk.

Fastlane and Holidays

As many of you are painfully aware, the NSF deadline for theory proposals is this Monday, Feb 19. As you may have also realized, Feb 19 is a federal holiday. According to NSF guidelines, in such an event, the deadline moves to the next working day (i.e the 20th) and I’ve confirmed that this is a correct interpretation for this deadline.

However, does Fastlane itself know this ? Suppose Fastlane refuses to accept any proposal submitted after Feb 19 (since in principle it has the information on the call and the deadline) ? Can the program manager then override it ?

I wonder if anyone has any experience with this…

Some good news on funding the NSF

As has been reported in many places, the House has passed a new spending bill that puts back many of the American Competitiveness Initiative funding that was proposed for FY07. This bill was passed in agreement with the Senate, so Senate passage is hopefully forthcoming next week, when it’s taken up there.

There are some differences in the level of the increase. According to Peter Harsha at the CRA blog,

Under the agreement, NSF would receive a 6 percent increase, slightly below the 7.8 percent increase called for in the ACI, but $335 million more than FY 2006.

But according to the AAAS funding update,

The National Science Foundation (NSF) would receive the full requested increase of 7.7 percent or $334 million for its core Research & Related Activities (R&RA) account to $4.7 billion. This funding would allow most research directorates to reverse declining funding of recent years with increases of between 6 and 8 percent. Total NSF R&D would climb 7.0 percent to $4.5 billion within a total budget of $5.9 billion, reversing two years of cuts in 2005 and 2006

Of course, the President still has to sign the bill. But since the ACI was his idea, one can be hopeful.

It could be one of my students…

A posting on comp.theory:

I just started a new class recently and am in need of a good class
project.
The course is a graduate course in computational geometry.
I think I will like this course but, overall, I don’t find myself too
much interested in teh material
I figure a good project will help motivate me through the course and,
well, a project is required anyway!
My main interests are in number theory and cryptography.
Any suggestions for a nice little project that could be done in the
span of several weeks by a beginning graduate student? The idea could
either be theoretical or an implementation in code or perhaps a bit of
both.

I have to ask: how does this person know they will like the course if they are not interested in the material ?

Designing homeworks

I’m teaching CG this semester, and it’s a lot of fun to go back and read some of the older texts and papers. Preparata and Shamos is actually quite a neat book, chock full of useful tricks and techniques; if only they had better ways of describing their algorithms …

The real challenge is designing good assignment problems, and I’ve almost given up on this. With the number of courses available on the web, and the amount of information accessible via Google, I’m hard pressed to write down a question that can’t be solved using Google and a few keywords. Even the trick of digging up interesting lemmas from related papers doesn’t work if you mention the paper in class. Or maybe I’m underestimating my students’ potential desire to solve the problem themselves.

And this is a problem how ?

On Harvard’s search for a new president:

The growing financial importance of research also could pressure Harvard to tap a scientist, something it hasn’t done since 1933.

But Harvard also could go the other way — picking a nonscientist who could rise above turf battles and reassure the rest of the school that America’s oldest and richest university isn’t becoming a giant science lab.

I don’t get it. Being a giant science lab is a BAD thing ?