|
|
We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. Some classic examples of perfect graphs are bipartite graphs, complements of bipartite graphs, line graphs of bipartite graphs, and their complements. It has been conjectured that any Berge graph either belongs to one of these four basic classes or can be decomposed in certain ways into smaller basic pieces.
Recently we have been able to prove a statement similar to that, except that we need five basic classes instead of four, and consequently, the Strong Perfect Graph Theorem.
This is joint work with Neil Robertson, Paul Seymour and Robin Thomas.
Andy Conn
IBM
Error estimates and poisedness in multivariate polynomial interpolation
and derivative-free optimization
Much of nonlinear optimization depends upon using models for the
problem, for example "Trust Region Methods". Moreover, for efficient
algorithms these models need to be sufficiently accurate.Typically they are
Taylor series based. In derivative free optimization we need to use other
models.
We show how to derive error estimates between a function and its
interpolating polynomial and between their corresponding derivatives. We
will also indicate the relationship with the convergence of model based
algorithms. The derivation is based on the concept of well-poisedness for
the interpolation set, directly connecting the accuracy of the error
estimates with the geometry of the points in the set. Prior existing error
estimates make use of less intuitive geometrical conditions.
This is joint work with Katya Scheinberg and Luis Vicente.
Gerard Cornuejols
Carnegie Mellon University
Recent Advances in Cutting Plane Theory
In this talk, we survey several classical cutting planes
for mixed integer programs. In particular, we discuss
the relation between split cuts, Gomory mixed integer
cuts and intersection cuts. These connections are then
used to generate better cutting planes (joint work with
Kent Andersen and Yanjun Li).
Zonghao Gu
ILOG Cplex
Quadratic Programming and Mixed Integer Quadratic Programming: Algorithms and Implementation
We see a growing interest in the
financial services industry for mixed integer
quadratic programming (MIQP), particularly as it applies to the solution of
mean-variance portfolio optimization models. A crucial component in such
techniques, as in mixed integer linear programming, is the ability to quickly
reoptimize the relaxations that occur at the nodes of the search
tree as a result of adding new variable bounds. While effective
implementations of algorithms for the solution of quadratic
programming (QP) problems have existed for some time, to our
knowledge effective implementations of QP algorithms with
restart capabilities, such as simplex-based algorithms, have not
been available. We will discuss the new, simplex-based QP algorithms
that have been implemented in CPLEX, and the key issues
that arose in developing these algorithms. Their performance
will be compared to the CPLEX barrier algorithm as applied to convex QPs.
David Shmoys
Cornell University
Approximation algorithms for facility location and network design problems
There has been a great deal of recent progress in research on the design
and analysis of approximation algorithms for NP-hard problems, thereby
expanding the breadth and depth of techniques used in this area.
For relatively simple models, such as the uncapacitated facility
location problem and the k-median problem, there are now several approaches
that yield algorithms with strong performance guarantees. Furthermore,
there are also a number of significant generalizations and variants for
which comparable results can be obtained, such as extensions that incorporate
notions of fault-tolerance (in facilities serving demand points) or in
requiring additional connectivity properties (e.g., among the facilities).
We shall survey some of the ideas (for both the algorithms' design and
analysis) that have been used in obtaining these results.
Mikkel Thorup
AT&T Research
Load Optimal MPLS Routing With N+M Labels
MPLS is a relatively new routing protocol for internet routers,
currently being deployed by many large ISPs, which assigns labels to
packets which control their routing. One use of MPLS is traffic
engineering, specifing routes to control link loads. Previous work on
this specified traffic paths using at least N^2 labels in the worst
case. However, an interesting feature of MPLS is that a single label
can specify a tree from all sources to a given destination.
We show
that a basic solution to minimum-cost multi-commodity flow problems
can be decomposed into at most N+M such trees. Thus we get optimal
load-based traffic engineering with at most N+M labels.
In addition to the theoretical results, we report on some experiments
demonstrating the actual gains on some concrete networks. Also, we
will discuss MPLS in some more detail, pointing to some natural
optimization problems that arises.
Robert Weismantel
Uni. Magdeburg
From Integral Bases to an Integer Programming Algorithm
This talk deals with the design of a
new integer programming algorithm
that is based on the theory of irreducible sets of points.
We will explain the latter issue in detail and demonstrate on
computational results that this approach is promissing.
Peter Winkler
Bell Labs
Graph Coloring and Optical Networks
Technology keeps changing in the optical communications world, but
somehow graph coloring is always in the picture. We'll give some examples
of new problems requiring (1) old theorems, (2) new theorems, and (3) new
conjectures. Along the way we will report on some joint work with Bell
Labs colleagues Penny Haxell, Gordon Wilfong and Lisa Zhang.
Steve Wright
University of Wisconsin
Solving Stochastic Optimization Problems on Computational Grids
We discuss a bundle/trust-region algorithm for solving two-stage
linear stochastic programming problems with recourse and its
implementation on a computational grid. Grids are parallel computing
platforms assembled from workstations, PCs, PC clusters, and
conventional parallel computers. We discuss results obtained by using
our code in conjunction with sampling techniques to solve many
instances of sampled approximations with large sample sizes. We are
able to obtain high-quality solutions to several benchmark problems in
the literature, and to explore various properties of these problems,
such as the size and dimensionality of the solution set and its
sensitivity.
This talk represents joint work with Jeff Linderoth (Lehigh
University) and Alex Shapiro (Georgia Tech).