__CS566A: Class
Presentations (Fall 2004)__

*Please email Bohdan at *beezer(at)cs.mcgill.ca*
if you find any errors or have questions.*

**Important:**
Presentations will be held: Nov. 23, 25 and 30. You will work in teams of two.
Each team presentation is for 20 minutes followed by 5 minutes of questions.
Your topic should be registered with Bohdan (email is OK: beezer AT cs.mcgill.ca) by November 11.
Give him your source document title, authors, journal name or URL.

Deadline for receiving all written material: Friday, Dec 3 at noon in Prof. Avis' mail box in
McConnell 318

**(1) Yu Jia Yuan **** **

Title:Resource allocation using linear programming in communication systemsPaper: ``On the use of linear programming for dynamic subchannel and bit allocation in multiuser OFDM'' Authors: Inhyoung Kim, Hae Leem Lee, Beomsup Kim and Y. H. Lee Journal: Global Telecommunications Conference, IEEE, 25-29 Nov. 2001 pp:3648-3652 Paper Online: Lecture Notes: here

**(2) Denis Dube**** **

Title:Solving linear arithmetic constraints for user interface applicationsPaper: Solving linear arithmetic constraints for user interface applications Authors: Alan Borning, Kim Marriott, Peter Stuckey, Yi Xiao Journal: Proceedings of the 10th annual ACM symposium on User interface software and technology Paper Online: http://portal.acm.org/citation.cfm?id=263518 Lecture Notes:

**(3) Letian Wang **** **

Title:Linear Programming on DEA methodsPaper: Measuring the efficiency of decision making units Authors: Charnes, A., W. W. Cooper, et al. Journal: European Journal of Operations Research 2(6): 429-44 (1978) Lecture Notes:

**(4)Esbensen, Eystein **** **

Title:Multistage Recourse Models and Scenario TreesPaper: An Introductory Tutorial on Stochastic Linear Programming Models Authors: Suvrajeet Sen (University of Arizona) and Julia L Higle (U of Arizona) Journal: INTERFACES 29: March - April 1999 pp 33-61 Lecture Notes:

**(1) Perouz Taslakian **** **

Title:Linear Programming and the Carpenter's RulerPaper: Straightening Polygonal Arcs and Convexifying Polygonal Cycles Authors: R. Connelly, E.D.Demaine and G.Rote Journal: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 432-442. Paper Online: http://theory.lcs.mit.edu/~edemaine/papers/FOCS2000a/ Lecture Notes:

**(2) Matthew Garde **** **

Title:Boosting and Linear ProgrammingPapers: Grove, A., and Schuurmans, D. Boosting in the limit: Maximizing the margin of learned ensembles. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98). Madison, WI, 1998. Demiriz, A., Bennett, K.P., and Shawe-Taylor, J. Linear programming boosting via column generation. Machine Learning, 46, 225-254, 2002. Schapire, R.E. The Boosting approach to machine learning: An overview. MSRI Workshop on Nonlinear Estimation and Classification, 2002. Lecture Notes:

**(3) Michal Havas ** and **Ivayla Tzvetkov **

Title:Detecting Buffer Overrun via LP'sPaper: Buffer Overrub Detection using Linear Programming and Static Analysis Authors: V. Ganapathy and D. Chandler Journal: CCS'03 ACM Proceedings Paper Online: via ACM site Lecture Notes:

**(4) Beste Kucukyazici **** **

Title:Modular Capacitated Location ProblemPaper: A Lagrangean Heuristic for a Modular Capacitated Location Problem Authors: Isabel Correia, M. Eugenia Captivo Journal: Annals of Operations Research; Sep 2003; 122; 1/4; pg.141

**(1) David Titley-Peloquin ** ** **

Title:Cycling in the Simplex MethodPaper: Hoffman's Circle Untangled Authors: Jon Lee Journal: Siam Review, Vol. 39, No. 1, March 1997, pp.98-105 Paper Online: via www.jstor.org Lecture Notes:

**(2) Ian Reid **** **

Title:Modelling Protein Folding with Linear ProgrammingPaper: RAPTOR: Optimal Protein Threading by Linear Programming Authors: Jinbo Xu, Ming Li, Dongsup Kim, and Ying Xu Journal: Journal of Bioinformatics and Computational Biology 1(1):95-117 (2003) Paper Online: Lecture Notes:

**(3) Ahad Dehghani**** **

Title:Travelling Salesman ProblemPapers: 1) Integer Programming Formulation of Traveling Salesman problems. C. E. Miller, A. W. Tucker, and R. A. Zemlin 2) On a Linear-Programming, Combination Approach to the Traveling-Salesman Problem G.B. Dantzig; D. R. Fulkerson; M. Johnson Lecture Notes:

**(4) Christelle Molle**** **

Title:Integer Programming and Sports : The Traveling Tournament ProblemPaper: The traveling tournament problem Description and Benchmarks Authors: Kelly Easton, George Nemhauser, Michael Trick Paper online at http://mat.gsia.cmu.edu/TOURN/

Last update: November 1st, 2004