The ACO seminar (1999-2000)
The ACO seminar (1999-2000)
| Fall 1999: | The seminar is in Porter Hall A19 most Tuesdays from 4:30pm to 6:00pm. |
| Spring 2000: | The seminar is in Tepper Cooper Auditorium most Tuesdays from 4:30pm to 6:00pm. |
Introduced by B. Bollob\'as, G. Brightwell, and J. Ne{\v s}et{\v r}il in 1986, parameter $c(G)$ of a graph $G$ is defined as the minimum number of edges one needs to delete from $G$ in order to obtain a cover graph. Extending their results we prove that for any $\delta >0,$ $(1-\delta) {1\over l} {n^2p\over 2} \le c({\mathcal G}_{n,p}) \le (1+\delta) {1\over l} {n^2p\over 2}$ asymptotically almost surely as long as $C n^{-1 + {1\over l} } \le p(n) \le c n^{-1 + {1\over l-1} }$ for some positive constants $c$ and $C.$ Here, as usual, ${\mathcal G}_{n,p}$ is the random graph. We will also discuss the main tools used: a version of Szemerédi's regularity lemma for sparse graphs due to Y. Kohayakawa and V. Rödl, and a counting lemma by B. Kreuter and Y. Kohayakawa on the size of a special class of graphs which avoid short cycles.
This is joint work with Robert Carr, Srinivas Doddi and Madhav Marathe.
This is joint work with John Hooker and Greger Ottosson.
This talk will discuss a partial description of the cycle polytope of a digraph G, i.e. the convex hull of incidence vectors of directed cycles of G.
Central to the talk is a method to derive facets of the cycle polytope from facets of the Asymmetric Traveling Salesman polytope via lifting and projection. Facets unrelated to the ATS polytope will also be discussed; in particular, we will give a complete characterization of those facets that cut off the origin.
The work on which we report is joint with Maarten Oosten. A technical report is available upon request.
The crossing numbers of K_n and K_m,n have long been conjectured to be [n/2][(n-1)/2][(n-2)/2][(n-3)/2]/4 and [m/2][(m-1)/2][n/2][(n-1)/2], respectively. Constructions which show these quantities to be upper bounds for the respective crossing numbers have been established. Here we show the results of a computer program which has generated all optimal drawings of K_n for n <= 11, thus verifying the conjecture for the complete graph for all n <= 12. We use a stricter definition of equivalent drawings which removes some of the doubt concerning the original enumerative approach to classifying the optimal drawings for n <= 10. Secondly, we associate to positive integers m and n a quadratic form which gives a lower bound for the crossing number of K_m,n. We show that if this quadratic form is copositive, then the conjecture holds for the particular values of m and n.
We will show how a theorem of Bridges and Ryser can be used to prove the Perfect Graph Theorem. Then we will present two theorems about minimally imperfect graphs. These theorems generalize earlier decomposition results on perfect graphs and they are, in turn, special cases of Chvatal's Skew Partition Conjecture.
This work is joint with Conforti, Gasparyan and Vuskovic. A paper (Perfect Graphs, Partitionable Graphs and Cutsets) is available upon request.
The Quadratic Knapsack Problem (QKP) is to maximize a positive quadratic boolean function subject to a linear capacity constraint. In this study an exact branch and bound algorithm for the QKP is proposed. In contrast with most of the solution algorithms in the literature, the one presented here is not restricted to nonnegative benefits. Upper bounds are obtained from a Lagrangian relaxation of a classical linearization of the problem reinforced with some families of valid inequalities. Due to the large number of constraints to be dualized a scheme akin to branch and cut, relax and cut, is used to dynamically guide the dualization process. Additionaly, a new primal heuristic for the problem that has improved considerably upon previous work is also proposed. Finally, a new way of randomly generating QKP instances that appear to be harder than the ones in the literature is also presented. Computational results are reported for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes (much larger than the ones in the literature) and also for known instances of the Max Clique Problem.
This is joint work with Abilio Lucena and Oscar Porto.
In this talk we look at relations between certain cuts for mixed 0/1 programs, derived from imposing the 0/1 condition on a single variable. The cuts we look at are the simple disjunctive cuts and the stronger mixed integer Gomory cuts, both obtained from the simplex tableau of the LP relaxation, and the lift-and-project cuts obtained by solving a higher dimensional linear program, called a cut generating linear program (CGLP).
The simple disjunctive cuts and the mixed integer Gomory cuts are obtained from a single row of the simplex tableau for a given basic solution. We will show that any lift-and-project cut can be obtained as a simple disjunctive cut from a certain choice of the LP relaxation basis. We will also show the converse, that any simple disjunctive cut can be written as a solution to the lift-and-project CGLP. If we consider integer strengthening of the lift-and-project cuts then the relationship will be between strengthened lift-and-project cuts and mixed integer Gomory cuts.
This relationship makes it possible to obtain an optimal lift-and-project cut by optimizing over basic solutions to the LP relaxation. We will outline how such a procedure can be implemented, where the basic step will be to identify a pivot that will lead to an improved basic solution. Some preliminary computational results on such an implementation will be presented.
This is joint work with Egon Balas.
If time allows we will consider other combinatorial problems arising in molecular biology.
In this talk, we will survey some graph-theoretical methods used to tackle the problem of finding minimum fill-in ordering for sparse Gaussian elimination. Nested dissection is a popular method in this area based on finding small node-separators in graphs. We will review the achievements of this method and its shortcomings and present two different variations motivated by trying to keep (i) the number of parallel steps in the elimination procedure and (ii) the fill-in introduced low respectively. Some experimental results will also be described.
This talk describes joint work with Claudson Bornstein, Bruce Maggs and Gary Miller.
Given a random graph, G, on n vertices, where each edge is included with probability p, what size independent set might one expect to find in G? I will talk about three results that seek to answer this question. Bela Bollobas's result deals with the case where p is a constant. Alan Frieze's result considers independent sets in sparser graphs, where p is smaller than n^(-1/3). In my recent work with Alan Frieze, we have generalized his work to answer the question, what is the largest independent set in G^b.
Many of the modern algorithms for solving constrained optimization problems generate iterates that follow certain continuous trajectories in the interior of the feasible region. These trajectories have their convergence point at an optimal solution which forms the motivation to follow them. The so-called central path is the best known of these trajectories and is used in path-following algorithms. In addition to the central path and its variations (weigthed centers, shifted centers) we will discuss primal-dual trajectories of vector fields arising from potential-reduction algorithms. We study the convergence properties of such trajectories as well as their asymptotic behavior. We will also comment on algorithmic implications of our results.
Documents linked from this page can be read using PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.
esth@cmu.edu