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

November 23rd

(1) Yu Jia Yuan

	Title: Resource allocation using linear programming in communication systems
	Paper: ``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 applications
	Paper: 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 methods
	Paper: 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 Trees
	Paper: 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: 

November 25th

(1) Perouz Taslakian

	Title: Linear Programming and the Carpenter's Ruler
	Paper: 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 Programming
		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's 
	Paper: 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 Problem	
	Paper: 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

November 30th

(1) David Titley-Peloquin

	Title: Cycling in the Simplex Method
	Paper: 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 Programming
	Paper: 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 Problem
		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 Problem
	Paper: 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