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.
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.
Ravi will finish the second part of his talk in this talk.
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.
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.
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.
Results on approximating MAX SAT within 3/4 and a PTAS for MAX CUT in dense graphs.
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.
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.
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.
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.
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 pageneils@andrew.cmu.edu