Algorithms Seminar/Fall11

From ResearchWiki

CS 7936: Heuristic algorithm design strategies

Wed 1:25-2:45pm

MEB 3147 (LCR)

Synopsis

You've been there before. After the long and futile attempts at finding an exact algorithm. After the proof of NP-hardness. After the hours spent trying to get a decent approximation, and the realization that the problem is impossible to even approximate in polynomial time. You could just do brute force search, but you might as well give up your identity as a computer scientist. The siren calls of a black box MATLAB library seems so soothing to your ears, but you feel deep down that THERE MUST BE A BETTER WAY.

If this person is you, then this seminar is the cure.

What we will cover are metaheuristics. These are algorithm design strategies that apply in a variety of (usually) optimization problems. While they usually don't have strong guarantees on behavior, they tend to work very effectively in practice. Gradient descent is a simple example, as is simulated annealing, or iterative reweighted least squares. Some heuristics actually do have formal guarantees in specific situations, but are often used outside that realm successfully. Gradient descent is again an example of this, as is alternating optimization.

The goal of the seminar is

• identify when such heuristics might be applicable to a given problem
• understand the formal limits on what these heuristics can and cannot do.
• (If time permits) study some of the associated complexity theory about heuristic search (what classes of problems admit good heuristic strategies, and how are these problems related to each other)

What is expected of you:

• read the prescribed papers
• make at least one full presentation on one of the topics
• participate in class discussions

You can take the seminar for anywhere between 1 and 3 credits: more credits means more presentation.

Participants

• Suresh Venkatasubramanian
• Parasaran Raman

Schedule