15850(C) Topics
This page will be filled out during the semester as we cover
the topics.
And here is a list of other topics which we considered,
some of which might be covered in the off weeks.
Dealer  Main Talk  Talk 1  Talk 2


Sleator
 Bauer
 Sleator
 Gleichauf

Required Readings
Don't panic, the first 2 are only short overviews and last is just a couple
tables.
Secondary Topics
Other Readings
Useful Links
Dealer  Main Talk  Talk 1  Talk 2


Miller
 Rochberg
 Miller
 Wong

Required Readings
Secondary Topics
Other Readings
Useful Links
Dealer  Main Talk  Talk 1  Talk 2


Blelloch
 Visitor?
 Gleichauf
 Blelloch

Required Readings
Secondary Topics
Other Readings
J. P. Ignizio and T. M. Cavalier,
Linear Programming,
Prentice Hall, 1994
Jorge J. More and Stephen J. Wright.
Optimization software guide.
SIAM, 1993.
Bradley, Hax and Magnanti.
Applied Mathematical Programming.
AddisonWesley, 1976.
G. L. Nemhauser, A.H.G. Rinnooy Kan, and M. J. Todd (ed.).
Optimization.
Elsevier, 1989.
M. Bazaraa, J. Jarvis, and H. Sherali.
Linear Programming and Network Flows.
Wiley, 1990.
Useful Links
Linear Programming Faq (includes a list of other web links).
Operations Research Page
Applications
Online Companies
that sell linear programming products (see the bottom of the page).
Interior point archive (includes many online papers).
Did Karmarkar deserve a patent? (a discussion)
A course
on linear programming and related topics with
online course notes.
A list of applications of
linear and integer programming for the DELTA airlines, American Airlines,
Northwest Airlines, UPS, Coca Cola, and the federal highway
commission.
Dealer  Main Talk  Talk 1  Talk 2


Blelloch
 Blelloch
 Harkavy
 Narlikar

Required Readings
Bradley, Hax and Magnanti.
Applied Mathematical Programming.
Chapter 9 (Integer Programming)
This chapter both has an introduction to the various application areas
of integer and mixedinteger programming and an
introduction solution techniques
including Branchandbound and cutting plane techniques.
R. Subramanian, R. P. Scheff, Jr., J. D. Quillinan, D. S. Wiper, and R. E.
Marsten.
Coldstart: Fleet assignment at Delta Air Lines.
(abstract).
The paper states that Delta saves $300 Million a year by using
mixedinteger programming to schedule their fleet.
Secondary Topics
Crew Pairing.
See Anbil, Tanga and Johnson, A global approach to crewpairing
optimization
(abstract).
Financial Models.
See Dahl, Meeraus and Zenios, Some financial
optimization models: II Financial engineering,
In Financial Optimization.
Branch and Bound Methods.
Other Readings
Most of the readings under linear programming have material on integer
programming. In addition, the following references are particularly
strong on integer or mixed integer linear programming. The list
also includes some applications.
George L. Nemhauser and Laurence A. Wolsey.
Integer and combinatorial optimization.
Wiley, 1988.
H. M Salkin and K. Mathur.
Foundations of Integer Programming.
NorthHolland, 1989.
J. Abara.
Applying integer linear programming to the fleet assignment
problem.
(abstract).
Stavros A. Zenios (ed.).
Financial optimization.
Cambridge University Press, 1993.
Useful Links
Linear Programming Faq (includes a list of other web links).
Operations Research Page
Applications
NEOS Guide (good background reading).
Online Companies
that sell linear programming products (there are also 100s which are
not online).
A list of applications of
linear programming for the DELTA airlines, American Airlines,
Northewest Airlines, UPS, Coca Cola, and the federal highway
commission.
Dealer  Main Talk  Talk 1  Talk 2


Sleator
 Sleator
 Talmor
 Birkedal

Required Readings
Cormen, Leiserson and Rivest, Introduction to Algorithms.
Chapter 27 (Maximum Flow).
Goldberg's algorithm for maximum flow in perspective: a computational
study. R. J. Anderson and J. C. Setubal.
In Network Flows and Matching.
This has some nice experimental results that compare several different
maximum flow algorithms over a variety of graph types.
Secondary Topics
Modeling Traffic.
See D. J. Zawack and G. L. Thompson.
A dynamic spacetime network flow model for city traffic
congestion.
(abstract).
MinCost Flow. See
An Efficient implementation of a scaling minimumcost flow algorithm,
Andrew V. Goldberg. STANCS921439.
This gives a brief description of the successive approximation pushrelabel
method of Goldberg and Tarjan (the stateoftheart).
What is more interesting, however, are the experimental results.
Other Readings
R. Ahuha, T. Magnanti and J. Orlin,
Network flows: theory, algorithms, and applications
Prentice Hall 1993.
Network Flows and Matching:
First DIMACS Implementation Challenge,
David Johnson and Catherine McGeoch (editors). AMS, 1993.
Useful Links
Networkflow codes and models (FTP directory).
Bibliography on Network Flow Problems
Dealer  Main Talk  Talk 1  Talk 2


Blelloch
 Bern
 Ghuloum
 Hardwick

Required Readings
F. Aurenhammer, Voronoi diagrams a survey of a fundamental
geometric data structure, ACM Computing Surveys, 1991, 345405.
Scot Drysdale, Voronoi Diagrams: Applications from Archaology to Zoology.
Review the applications described in Eppstein's
Voronoi
Diagram's Page.
Secondary Topics
Mesh Generation.
See
The Finite element mesh generation page
The Meshing Research Corner (here at CMU)
M. Bern and D. Eppstein, Mesh generation and optimal triangulation,
in "Computing in Euclidean Geometry", 2nd edition, World
Scientific, 1995.
T.J. Baker, Developments and trends in 3d mesh generation,
Appl. Numer. Mathematics, 1989, 275304.
Surface Reconstruction.
See
G. Barequet and M. Sharir, Piecewiselinear interpolation
between polygonal slices, 10th ACM Symp. Computational Geometry,
1994.
Application of Delaunay triangulation to Interpolation.
Other Readings on Algorithms
Preparata, Franco P.
Computational geometry: an introduction.
SpringerVerlag, 1988.
O'Rourke.
Computational Geometry in C.
Cambridge University Press, 1994.
J. Nievergelt and K. Hinrichs.
Algorithms and data structures:
with applications to graphics and geometry.
Prentice Hall, 1993.
Other Readings on Applications
Okabe, Boots, and Sugihara,
Spatial Tesselations: Concepts and Applications of Voronoi Diagrams,
Wiley, 1992.
J.D. Boissonnat and B. Geiger,
Threedimensional reconstruction of complex shapes
based on the Delaunay triangulation, in "Biomedical I
Processing and Biomedical Visualization", Acharya and Goldgof, eds.,
SPIE, 1993, 964975.
M. Polis and D. McKeown, Issues in iterative TIN generation
to support large scale simulations, AUTOCARTO 11, 1993.
H. Edelsbrunner and E. Muecke, Threedimensional alpha shapes,
ACM Trans. Graphics, 1994, 4372.
Useful Links
Geometry in
Action, an excellent page on applications of computational geometry
The computational geometry pages. Another page on computational geometry.
Yahoo's Geometry page.
Finite element mesh generation.
Application of Delaunay triangulation to Interpolation.
An experimental comparison of various Delaunay algorithms.
Includes MPEG movies of the algorithms in action (if you dare wait for them to arrive from Germany).
Companies that sell products that use Delaunay triangulation:
A long list of grid generators at Silicon Graphics.
ANSYS
SDRC
ICEM CFD
Fluent (Rampant)
Dealer  Main Talk  Talk 1  Talk 2


Miller
 Miller
 Boyan
 Bern

Required Readings
N. Sherwani,
Algorithms for VLSI Physical Design Automation,
Kluwer, 1993.
Secondary Topics
Other Readings
T. Lengauer,
Combinatorial algorithms for integrated circuit layout,
Wiley 1990.
B. Korte, L Lovasz, H. J. Promel, and A. Schrijver (eds.).
Paths, flows, and VLSIlayout.
Springer Verlag, 1990.
Useful Links
Industrial CAD Sites
on the Web.
University of Idaho's Links
to VLSI information.
The use of combinatorial algorithms in
VLSI routing problems
A good page of
algorithms
used in VLSI CAD (University of Virginia).
Dealer  Main Talk  Talk 1  Talk 2


Miller
 Birkedal
 Miller
 ReidMiller

Required Readings
Arthur M. Lesk.
Computational molecular biology:
sources and methods for sequence analysis.
Oxford University Press, 1988.
Secondary Topics
Other Readings
Useful Links
A very good bibliography on the topic.
A course
on Algorithms for Molecular Biology. Includes many references.
A bibliography on Computational Gene recognition.
Sequence analysis software
Human
Genome Project Information including a Primer
on Molecular Genetics.
Dealer  Main Talk  Talk 1  Talk 2


Blelloch
 Blelloch
 Leon
 Bauer

Required Readings
The Numerical Solution of the NBody Problem, L. Greengard
(abstract).
Nbody/Particle simulation Methods.
An excellent online overview of the various nbody methods.
Here is a local copy since the connection
is slow.
Secondary Topics
Other Readings
Fast algorithms for classical physics, L. Greengard
(abstract).
A hierarchical O(N Log N) force calculation algorithm.
J. E. Barnes and P. Hut. Nature, 324(4):446449, December 1986.
Fast parallel tree codes for gravitational and fluid dynamical
Nbody problems. Salmon, Warren and Winckelmans.
(abstract).
Scalable variants of multipolebased algorithms for molecular
dynamics applications
Board, Hakura, Elliot, and Rankin.
(abstract).
Optimal parallel allnearestneighbours using the wellseparated
pairs decomposition.
P.B. Callahan. In 34th Annual Symposium on Foundations of Computer Science, pages 332340, Palo Alto, 1993. IEEE.
Astrophysical nbody simulations using hierarchical tree data
structures.
M. Warren and J. Salmon. In Proceedings of Supercomputing, 1992.
Useful Links
Dealer  Main Talk  Talk 1  Talk 2


Sleator
 Sleator
 Juarez
 Rochberg

Required Readings
Secondary Topics
Other Readings
Everitt, Brian.
Cluster analysis (2d ed.).
Halsted Press, 1980.
Useful Links
Here are some other areas in which algorithms are used in the real world.
Indexing (i.e. for web crawlers)
Robot navigation
Linear System's solvers
Graphics
Speech recognition
Computer vision
Machine learning
Guy Blelloch, blelloch@cs.cmu.edu.