EECS 6118 : Project Info
- The course project is intended to lead
the student towards some advanced research topics in optimization,
algorithmic
techniques and their applications.
- You may refer to various major published sources, the
course references, and related
periodicals to choose a project topic.
- A project can be any of the following:
- a theoretical
study of an optimization problem or optimization method,
- an original
survey of an optimization topic, related background, techniques,
algorithms, open problems, etc.,
- experimental implementation of
optimization algorithms.
- The grading will be based on timeliness,
clarity of presentation, documentation, coding (if applicable),
and the extent of originality .
Time
Table:
Project
Proposal (by the end of the 2nd month in the term)
- Choose a project topic:
- start thinking about this as early as possible. It might take
some time until you decide on a suitable topic.
- A suggested list of project topics and
sources appears below.
- Consult with me about the suitability of your chosen project topic, especially if it is not on the suggested list.
- Email me one or two paragraphs explaining what the topic is
about, a few
tentative sources that you plan to use, and the motivation behind choosing that
particular topic.
Final
Report &
Presentation (last lecture hour)
- Submit the final
hard copy written version of your project
report.
This should include pointers to your accessible on-line documents and
codes (if applicable).
- Give a 15-minute
presentation of your project in class.
This may include a demo of impelmentation, theoretical and
empirical results.
Some Past Projects:
- Parameter Optimization in Computer Vision Modeling, by Yulia Kotseruba, 2012.
- [Wireless] Network Coding Optimization, by Alireza Moghaddam, 2012.
- Integrating Prior Knowledge in Time Series Allignment [in Signal Processing]: Prior Optimized Time Warping, by Xiaoguang Yan, 2012.
- A Study on Kernel Functions for Text-Processing, by Celso Kaestner, 2012.
- A Study on a Newton-type Algorithm and its Application in Machine Learning, by Ying Li, 2012.
- Resource Allocation in the Cloud by using Distributed Optimization Techniques, by Hongbin Lu, 2012.
- Small Approximation of epsilon-Pareto Sets of Team Formation in Social Networks, by Morteza Zihayat, 2012.
Suggested new project topics and reading list:
- Project 1: A linear system of equations Ax = b
can be solved by either direct methods (Gaussian elimination, LU
decomposition ...) or
by
iterative methods (preconditioned conjugate gradient ...). Direct
methods are more suitable for dense small systems. Iterative methods
are preferable for large sparse systems such as social networks. These
methods are based on minimizing the convex quadratic
function f(x) = 1/2 xTAx - bTx
by iterative gradient methods (assuming A is positive semidefinite, such
as the Laplacian of a graph). These methods are an alternative to the
Ellipsoid and
Interior Point Methods for general convex optimization that we study in
Slides 6 and 7. Research papers: [1,2]. General background sources: [3,4,5].
- Project 2: Graph cuts and flows. Research papers: [6, 7]. General background sources: [3, 4, 5].
- Project 3: Linear
Programming: alternative weakly polynomial-time algorithms than the Ellipsoid and Interior Point Methods, and the
quest for a strongly polynomial-time algorithm. Research papers: [8, 9, 10]. Additional sources: [11, 12].
- Project 4: Multiplicative weights update: a combinatorial method for solving Semidefinite Programs. Research papers: [13, 14]. General source: [15].
- Project 5: Several sub-topics in Computer Science Theory for the Information Age. General Source: [16].
References:
- J. Kelner, L. Orecchia, A. Sidford, "A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time," Proc. Symposium on Theory of Computing (STOC), 2013.
- J. Dunagan, N. Harvey, "Iteratively Constructing Preconditioners via the Conjugate Gradient Method," STOC 2007.
- J. Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain," 1994.
- C. Godsil, G. Royle, "Algebraic Graph Theory," Springer, 2001.
- D. Spielman, "Lecture Notes: Spectral Graph Theory," 2012.
- P. Christiano, J. Kelner,
A. Madry,
D. Spielman,
S.-H. Teng, "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs," STOC 2011.
- S. Arora, S. Rao, U. Vazirani, "Expander Flows, Geometric Embeddings and Graph Partitioning," STOC 2004.
- M. Barasz, S. Vempala, "A New Approach to Strongly Polynomial Linear Programming," Innovations in Computer Science, 2010.
- J. Kelner, D. Spielman, "A Randomized Polynomial-Time Simplex Algorithm for Linear Programming," STOC 2005.
- J. Dunagan, S. Vempala, "A Simple Polynomial-time Rescaling Algorithm for Solving Linear Programs," STOC 2004.
- E. Tardos, "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Resaerch 34(2), pp: 250-256, 1986.
- E. Hazan, "Lecture Notes: Polynomial Time Algorithms for Linear Programming," 2011.
- S. Arora, E. Hazan, S. Kale, "The Multiplicative Weights Update Method: a Meta Algorithm and Applications," Journal of Theory of Computing, 2010.
- S. Arora, S. Kale, "A Combinatorial, Primal-Dual approach to Semidefinite Programs," STOC 2007.
- L. Lovasz, "Lecture Note: Semidefinite programs and combinatorial optimization," 1995.
- J. Hopcroft, R. Kannan, "Computer Science Theory for the Information Age," to be published soon.