Last year's seminar talks are summarized here.

TITLE:

SPEAKER: Alan Frieze

WHEN: Monday, Sep 9. 3:30 - 4:30

WHERE: Wean Hall 8220

There has recently been some success in designing polynomial time approximation schemes for dense optimisations problems such as MAX-CUT. Intuitively a problem is dense if its optimal value is within a constant factor of the maximum for the problem class. We survey some of these results.

TITLE:

SPEAKER: George Christopher

WHEN: Monday, Sep 16. 3:30 - 4:30

WHERE: Wean Hall 8220

Circular decomposable metrics (CDM) are sums of cut metrics that satisfy a circularity condition. A number of combinatorial optimization problems, including the traveling salesman problem, are easily solved if the underlying cost matrix represents a CDM. We give a linear time algorithm for recognizing CDMs and show that they are identical to another class of metrics: the Kalmanson metric.

TITLE:

SPEAKER: Victor Grinberg

WHEN: Monday, Sep 30. 3:30 - 4:30

WHERE: Wean Hall 8220

Assume 2 ordered chains of elements are given and the goal is to merge them
by means of pairwise comparisons. This procedure is used as a step in many
sorting algorithms. Let *M*(*m*,*n*) denote the minimal
number of pairwise comparisons which will suffice to merge 2 chains of
lengths *m* and *n* in the worst case. Upper bounds for
*M*(*m*,*n*) correspond to good merging algorithms, while
lower bounds set limits for **any** merging algorithm. In the first part of
the talk we give an outline of the study of the function *M*(*m*,*n*).

In the second part of the talk we shall consider the **parallel** merging problem,
where non-overlapping comparisons are allowed to be united into **stages**
and performed simultaneously. In this case we are interested in *P*(*m*,*n*)
the minimal number of stages which will suffice to merge 2 chains of lengths *m* and *n*
in the worst case. A new lower bound for *P*(*m*,*n*) will be proved. Combining
it with the upper bound obtained by K.~E.~Batcher (1968), we obtain the following
final result: *P*(*m*,*n*)=ceil(log(*m*+*n*)) for all *m*, *n*.

TITLE:

SPEAKER: Ravi Kannan

WHEN: Monday, Oct 7. 3:30 - 4:30

WHERE: Wean Hall 8220

We will describe a new algorithm to find a ``regular'' partition of a graph (which I will define). Using this, we are able to find approximate solutions to the Max Cut, Multi way cut and in fact any MAX-SNP problem in dense graphs in CONSTANT time (by a Monte Carlo algorithm).

TITLE:

SPEAKER: Colin McDiarmid

WHEN: Monday, Oct 21. 3:30 - 4:30

WHERE: Wean Hall 8220

Suppose that we have a graph, with a source *s* and a sink *t*, and with capacities
on the edges. In the classical network flow problem we want to pack *s*-*t* paths,
so that the number of times an edge is used is at most its capacity.
If we must not pack the paths too closely then we may want to pack caterpillars,
where a caterpillar consists of the edges in an *s*-*t* path together with the
edges incident with internal nodes of the path. We shall discuss this and
related problems, for general and for planar graphs and directed graphs.

TITLE:

SPEAKER: Richard Anderson, University of Washington

WHEN: Monday, Oct 28. 3:30 - 4:30

WHERE: Wean Hall 8220

In this talk, I will present results about
data structures for use in *N*-body simulation.
I will concentrate on the spatial decomposition tree used in
particle-cluster force evaluation algorithms such as the Barnes-Hut
algorithm. A *k*-d tree is asymptotically inferior to a
spatially balanced tree. The worst case complexity of
the force evaluation algorithm using a *k*-d tree is
*Theta*(*n* log³*n *log *L*) compared with *Theta*(*n* log *L*) for an
oct-tree. (*L* is the separation ratio of the set of points.)
I will also discuss methods for improving the constant factor of the algorithm,
and present several methods which improve over the standard oct-tree
decomposition. The results are
all directly applicable to practical implementations of *N*-body algorithms.

TITLE:

SPEAKER: Santosh Vempala

WHEN: Monday, Nov 4. 3:30 - 4:30

WHERE: Wean Hall 3412

We propose new geometric models and algorithms as tools for solving
problems in machine learning and for information retrieval.
Our success so far is two-fold: an efficient algorithm for learning
linear threshold functions (perceptrons)
which is tolerant to classification noise,
and an explanation of the success
of the information retrieval technique known as *Latent Semantic Indexing*
along with a provable speed-up of the same. Our proposal is to use
similar techniques to understand closely related open problems
such as learning the intersection of half-spaces.

Thesis Committee: Avrim Blum, Alan Frieze, Ravi Kannan, László Lovász.

TITLE:

SPEAKER: Giuseppe Lancia

WHEN: Monday, Nov 11. 3:30 - 4:30

WHERE: Wean Hall 8220

In this talk I will address some problems arising in computational molecular biology on which I have worked in the past few years. After an introductory review of some basic concepts of biology, I will address the following problems:

- Genome rearrangements by DNA inversions.
- Genotyping of pooled microsatellite markers.
- Multiple alignment problems.

TITLE:

SPEAKER: Robert Carr

WHEN: Monday, Nov 18. 3:30 - 4:30

WHERE: Wean Hall 8220

We outline proofs of bounds on the solutions of the 2-matching
and TSP problems. One of the reasons these bounds are important
is that they shed light on the longstanding conjecture that the minimum
cost Hamilton cycle is within 4/3 the cost of the optimum subtour solution
when the costs satisfy the triangle inequality.

This is joint work with Sylvia Boyd.

TITLE:

SPEAKER: Gabor Pataki

WHEN: Monday, Nov 25. 3:30 - 4:30

WHERE: Wean Hall 8220

In this dissertation we study the optimization problem:

(*P*) Minimize *cx* such that *x* in *K* and *Ax* = *b*

where *K* is a closed convex cone, *A* is a matrix, and *b*
and *c* are vectors of approppriate dimension.
Our problem is called a **cone programming problem**, or a cone-program.
In fact, every convex programming problem can be formulated as a cone-program, thus
(*P*) models essentially all efficiently (i.e. in polynomial time) solvable
optimization problems.

The most fundamental class of cone-programs is **linear programming**,
when *K* is the nonnegative orthant. Another important
class is **semidefinite programming**
(SDP), that gained a lot of attention recently.
Some other structured
convex programs, for which the results of this work apply, are:

- Convex Quadratic Programming.

- Matrix Approximation Problems.

- The optimization of **spectral** functions. Spectral functions
are functions defined on symmetric matrices, that depend only on the
eigenvalues of the matrix.

We develop a self-contained theory to describe

- The facial structure, in particular basic solutions of cone (and convex) programs.

- Nondegeneracy.

- Feasible directions.

- Simplex-type methods.

Our results are generalizations of the corresponding fundamental results
for linear programming, and are intuitively plausible to
geometric intuition. Nevertheless, with a few rare exceptions they have not been
given in the mathematical programming literature.
As a corollary, we obtain results explaining
the inherent nonsmoothness (i.e. nondifferentiability)
of several structured convex programming problems.

TITLE:

SPEAKER: Milind Dawande

WHEN: Monday, Dec 2. 3:30 - 4:30

WHERE: Wean Hall 8220

We present a new, inference logic based, approach to perform sensitivity analysis for mixed integer programming problems.

This is joint work with Prof. John Hooker.

Back to the ACO home page

neils@andrew.cmu.edu