Instructor: Ashish Goel
Handout 5: Project Descriptions
Given: 4/27/2006. Groups due: 5/3/2006.
You are also allowed to (and encouraged to) develop project proposals of your own. We would like to enforce group sizes of 4 as far as possible, but will allow groups of size 3 if absolutely necessary. If you need help forming groups, please consult with Brad Null at least a day or two before the deadline. We will make additional information (such as the constraints for the sports league project, more details of the travel engine project) available soon to the groups who choose those projects. Please send us your groups and a first and a second choice project by May 3rd.
Suggested projects:
Sports League Scheduling
Capacity: 2 groups
Description: In this project we ask the groups to develop a "good" schedule for the 2006-07 NBA season. The groups will be given a number of real world constraints and will be asked to derive one or more additional realistic constraints as well as a reasonable objective function on their own. The subsequent task will be to develop an algorithm that can be applied to these constraints and objective to produce a schedule. Be careful though, developing a "good" (much less "optimal") sports schedule is not a trivial problem and will likely require the groups to devise some heuristic extensions beyond the algorithms developed in this class.
Capacity: 2 groups
Finding optimum travel routing given the diverse sources of information on the web is a hard problem. This project involves developing and implementing an algorithm that can take in multiple criteria (pricing, flight length, start and stop times, etc.) and determine the k-best travel itineraries for a user. You will be expected to supply running, functioning code that can be applied to a data format that will be provided. In addition, certain design details (such as the definition of "best" and the determination of k) will be left up to the group.
Universal Portfolio
Optimization
Capacity: 2 groups
Read the paper “Efficient Algorithms for
Online Game Playing and Universal Portfolio Management” by Agarwal
and Hazan (and the papers by Cover referenced threrein for background). Then
implement the universal portfolio optimization techniques of Agarwal and Hazan.
Finally, compare the performance of your algorithm on the stocks included in
the S&P 500 (or the Nasdaq 100) to the respective index over a five year
period.
Keyword Pricing
Capacity: 2 groups
Description: You are given a set of merchants who
want to buy ad space on a search engine for a set of keywords. Merchant k has
utility U(k,j) (which is known only to him) per user-click on an advertisement
that appear when a user searches for keyword j. If the merchant is at position
i on the list of ads displayed for keyword j, his ad will get Q(j,k)P(i) total
clicks over the course of a day. The merchant has a budget B(k).The position of
a merchant’s ad for a specific keyword is determined by the outcome of an
online auction. Develop reasonable models for the distributions of U, B, P, and
Q and try to compute equilibrium bidding strategies for a set of merchants. Requires
either some minimal prior knowledge of game theory or some willingness to read
up the first two chapters of a game theory text, as well as the willingness to
read a couple of relevant papers by faculty in MS&E.
In addition, a student has submitted the following project. You can contact Brad if you would like to work on this project and we will put you in touch with the student.
Predicting depth from images.
I had proposed a algorithm that can predict depth from single still
images for 3-d reconstruction. To learn parameters, and predict depth
is a optimization problem. I would like to explore if depth prediction
accuracy improves with stereo images, and/or explore different
optimization for learning and prediction.