Name: Nikolaos Sahinidis
University: Carnegie Mellon University Dept. of Chemical Engineering
Date: Friday, April 18, 2008
Time: 3:30 to 5:00 pm
Location: Room 388 Posner Hall
Title: Optimization in the New Biology
Abstract:
A variety of modern bioinformatics and systems biology problems can be approached systematically from an optimization point of view. This talk will focus on protein side-chain prediction, protein structural alignment, structure determination from X-ray diffraction measurements, and metabolic systems analysis and design. To solve these problems, we have employed machinery from linear algebra, dynamic programming, combinatorial optimization, and mixed-integer nonlinear programming. Many of the underlying biological problems are purely continuous in nature but have, to this date, been approached mostly via combinatorial optimization algorithms that are applied to discrete approximations. Other problems naturally present a strong and difficult combinatorial component.
Title: A Polynomial Bound on Vertex Folkman Numbers
Speaker: Andrzej Dudek, Emory University
When: Tuesday April 15, 12:30-13:30
Where: Wean Hall 5304
Abstract:
In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every r coloring of vertices of H yields at least one monochromatic copy of G. His proof gives no good bound on the order of graph H, i.e., the order of H is bounded by an iterated power function of n. In this talk we will give an alternative proof of Folkman’s theorem with the relatively small order of H bounded from above by O(n^3 log^3 n). This is joint work with Vojtech Rodl.
Friday April 18th, 2008
3:30pm
WEH 7220
TITLE: What makes a good Steiner point?
Benoit Hudson
Toyota Technological Institute at Chicago
ABSTRACT:
The mesh refinement problem is to take an input geometry (defined by a set of points, curves, and surfaces), and output a set of points that both “respects” the geometry and has good “quality.” What it means for a tetrahedral mesh to respect curved surfaces is already interesting and will take some explaining. Even knowing what the goal is, mesh refinement algorithms typically are of the form: until the output is good enough, add points. But where should we add these additional Steiner points? And how do we know that the algorithm will stop? Most prior work is very specific about where to add points, and thus needs its own very specific proof that the algorithm ends.
In this talk, I will give a set of rules for choosing Steiner points. Any algorithm that follows my rules — as most previous algorithms do — will terminate. After hearing me out, you will know how to represent curved surfaces with linear elements, and you will be able to design your very own meshing algorithm with confidence.
