TITLE:

SPEAKER: R. Ravi

WHEN: Thursday, Oct 5. 3:30 - 4:30

WHERE: Wean Hall 8220

The purpose of this talk is twofold. First, basic terminology and background assumed in the Computational Biology literature will be introduced. Second, the seminar topics suggested in this area will be reviewed and the more important ones will be highlighted.

TITLE:

SPEAKER: Alexander Schrijver, CWI and Univ. Amsterdam.

WHEN: Thursday, Oct 12. 3:30 - 4:30

WHERE: Wean Hall 5205

Finding disjoint paths in a graph, between *k* specified
pairs of vertices, is an NP-complete problem, even if
the graph is undirected and planar. (This case is of
interest for VLSI-design.)
If we fix *k*, the problem is polynomially solvable for
undirected graphs (not necessarily planar), which is a
theorem of Robertson and Seymour.
In the directed case the problem remains NP-complete also
for fixed *k*. We discuss a polynomial-time algorithm for
fixed *k* and directed planar graphs. The algorithm is
based on cohomology over free groups.

TITLE:

SPEAKER: R. Ravi

WHEN: Thursday, Oct 19. 3:30 - 4:30

WHERE: Wean Hall 5205

Ravi will finish the second part of his talk in this talk.

TITLE:

SPEAKER: Bob Carr

WHEN: Thursday, Oct 26. 3:30 - 4:30

WHERE: Wean Hall 5205

This thesis defense will focus on the *cycle-shrink relaxation* and
*Chvatal derivations* of the Traveling Salesman Problem.
We will group TSP inequalities into classes in a natural way by considering
their Chvatal derivations. Every facet-defining TSP inequality will be put
in one of these classes. General characteristics of Chvatal derivations will
be discussed.

We then show how to use the cycle-shrink relaxation to separate over any of
these classes in polynomial time in the size of our fractional point *x**
that we wish to cut-off.

TITLE:

SPEAKER: Dr. Laurence A. Wolsey of CORE, Université Catholique de Louvain.

WHEN: Thursday, Nov 2. 3:30 - 4:30

WHERE: Wean Hall 5205

We describe a branch-and-cut program bc-opt for mixed integer programming based on the optimisation library of a commercial system. As part of the development of this system, we investigate the use of cutting planes for integer programs with general integer variables. We show how cutting planes arising from knapsack inequalities can be generated and lifted as in the case of 0-1 variables, and how continuous variables can also be introduced. Some heuristic ideas for tackling difficult models are also discussed. Finally we present results on a range of test problems arising from practical applications. This is joint work with C.~Cordier, H.~Marchand and others.

TITLE:

SPEAKER: Yury Smirnov

WHEN: Thursday, Feb 15. 3:30 - 4:30

WHERE: Wean Hall 8220

Consider the task of reaching a goal state in a partially or completely unknown domain. To accomplish such a task search algorithms have to explore the domain sufficiently to locate a goal state and a path leading to it, performing therefore what we call uninformed ``treasure hunt.'' Very often prior knowledge in the form of heuristic values estimating distances towards the goal state is readily available. A heuristic-driven strategy can be very successful: it can significantly outperform uninformed exploration-oriented approaches. However, heuristic values can be misleading: if we model the domain as a graph, the worst-case complexity of a heuristic-driven algorithm can be worse than linear in the weight of the graph (sum of all edge lengths).

Known exploration approaches can solve the uninformed ``treasure hunt'' problem with linear performance guarantees, but they cannot utilize heuristic values. Furthermore, their average-case (empirical) performance is usually much worse than that of heuristic-driven approaches even in uninformed problems. In its turn, known heuristic-driven algorithms can have more than linear worst-case complexity if heuristics are misleading.

We develop a new algorithmic framework for the heuristic-driven ``treasure hunt,'' called VECA, that combines the advantages of both approaches. We show that VECA provides linear performance guarantees, and that these guarantees do not come at the expense of a deterioration in average-case performance. As a by-product of our research, we also prove new results about the worst-case performance of other goal-directed exploration algorithms.

TITLE:

SPEAKER: David Williamson, IBM.

WHEN: Thursday, Feb 29. 3:30 - 4:30

WHERE: Wean Hall 8220

Results on approximating MAX SAT within 3/4 and a PTAS for MAX CUT in dense graphs.

TITLE:

SPEAKER: R. Ravi

WHEN: Thursday, Mar 14. 3:30 - 4:30

WHERE: Wean Hall 8220

An area of recent activity in computational biology is combinatorial algorithms for genome rearrangement. In the course of its evolution, the genome of an organism mutates by processes that can rearrange whole segments of a chromosome in a single event. These rearrangement mechanisms include inversion, transposition, duplication, and translocation, and a basic problem is to determine the minimum number of such events that transform one genome to another. This number is called the rearrangement distance between the two genomes, and gives a lower bound on the number of events that must have occurred since their divergence, assuming evolution proceeds according to the processes of the study.

In this talk, I will present joint work with John Kececioglu that appeared in SODA '95. This work undertook the first algorithmic study of genome rearrangement by translocation. A translocation exchanges material at the end of two chromosomes within a genome. We model this as a process that exchanges prefixes and suffixes of strings, where each string represents a sequence of distinct markers along a chromosome in the genome. For the general problem of determining the translocation distance between two such sets of strings, we present a 2-approximation algorithm. For a theoretical model in which the exchanged substrings are of equal length, we derive an optimal algorithm for translocation distance. Better algorithms have since been developed for some of the cases we addressed in this work. I will also outline some of the open problems in this area.

TITLE:

SPEAKER: Neil Simonetti

WHEN: Thursday, Apr 11. 3:30 - 4:30

WHERE: Wean Hall 8220

This paper discusses an implementation of a dynamic programming approach to the traveling salesman problem that runs in time linear in the number of cities. Optimality can be guaranteed when precedence constraints of a certain type are present, and many problems involving time windows fall into this class. Perhaps the most interesting feature of the procedure is that an auxiliary structure is built before any particular problem instance is known, reducing the computational effort required to solve a given problem instance to a fraction of what it would be without such a structure.

TITLE:

SPEAKER: Santosh Vempala

WHEN: Thursday, Apr 18. 3:30 - 4:30

WHERE: Wean Hall 8220

Given a graph, we can try to embed it in some Euclidean space so that adjacent nodes are represented by vectors satisfying some specific relation (orthogonal, distance 1, etc.). It has been observed that the existence of such representations in specific dimensions is closely related to interesting graph-theoretic properties. In fact, the construction of such a representation is often an important step in algorithms for computing, or estimating, various purely graph-theoretic invariants like chromatic number, connectivity and maximum cut.

We discuss a linear algebraic invariant introduced by Colin de Verdiére, which is related to various topological properties of a graph. Our main results are a geometric formulation of the invariant, and constructing representations of graphs by spheres, related to the classical result of Koebe about representing planar graphs by touching disks.

TITLE:

SPEAKER: Bruce Reed

WHEN: Thursday, Apr 25. 3:30 - 4:30

WHERE: Wean Hall 8220

The chromatic number of a graph of maximum degree, *D* is
at most *D*+1. In 1947, Brooks showed that if the clique size
in *G* is not *D*+1, then this inequality is strict. We generalize
this result, showing that the chromatic number of a graph of
maximum degree *D* is a convex combination of *D*+1 and the
size of a maximum clique in *G*. We present some related conjectures and
discuss related work of Molloy and Reed concerning Strong edge colouring
and total colouring.

TITLE:

SPEAKER: George Christopher

WHEN: Thursday, May 2. 3:30 - 4:30

WHERE: WeanHall 8220

An *n* by *n* matrix *D* is called a tree metric if there exists a tree *T*
on *n* vertices with weights on its edges such that *D*[*i*,*j*] equals the
sum of the weights of the edges in the unique path in *T* with endpoints
*i* and *j*. Bandelt and Dress defined totally decomposable metrics (TDM)
as an extension of tree metrics. TDMs also extend a wide range of
other metrics. For example: consider a set of *n* points *v*[1], ..., *v*[*n*]
which lie on the boundary of a convex region in the Euclidean plane.
The matrix with entry *d*[*i*,*j*] equal to the euclidean distance from
*v*[*i*] to *v*[*j*] is called a convex Euclidean metric. Convex Euclidean
metrics are TDMs. In fact an important subclass of TDMs called
circular decomposable metrics (CDM) has been defined as an extension
of convex Euclidean metrics. In this talk, we will explore the
structure of TDMs and CDMs. In addition, applications of these
classes of metrics to the TSP and the b-matching problem will be
discussed.

Back to the ACO seminar page

neils@andrew.cmu.edu