ACO The ACO seminar (1999-2000)

The current organizers of the ACO Seminar are Michael Perregaard (michael4@andrew.cmu.edu) and Erlendur S. Thorsteinsson (esth@cmu.edu). If you have questions or suggestions about the seminar, or want to be a speaker, please contact the organizers.

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.

Schedule:

 TITLE: On an extremal problem for random graphs.
SPEAKER: Lubos Thoma.
WHEN: October 5th, 4:30-6:00pm.
WHERE: Porter Hall A19.

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.

Joint work with V. Rödl.

TITLE: On the red-blue set cover problem.
SPEAKER: Goran Konjevod.
WHEN: October 19th, 4:30-6:00pm.
WHERE: Porter Hall A19.
PAPERS: In this talk about some work still in progress, we introduce a problem which generalizes set cover and some other previously investigated combinatorial optimization problems. We discuss these relationships and use them to formulate linear relaxations of red-blue set cover. Then we show that red-blue set cover is hard to approximate to within a factor of $O(2^{log^{1-\epsilon} n}$ for any $\epsilon$ (this is asymptotically more than polylogarithmic, but less than $n^\epsilon$ for any $\epsilon$). Finally, we give an algorithm with a sublinear approximation ratio for a fairly general restriction of the problem.

This is joint work with Robert Carr, Srinivas Doddi and Madhav Marathe.

TITLE: Improved Approximation Algorithms for Degree-Bounded Spanning Trees.
SPEAKER: Jochen Könemann.
WHEN: November 2nd, 4:30-6:00pm.
WHERE: Porter Hall A19.
PAPERS: We present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. In this problem, we are given a graph, a nonnegative cost function on the edge, and a positive integer $B^*$, and the goal is to find a minimum cost spanning tree $T$ with maximum degree at most $B^*$. In an $n$-node graph, our algorithm finds a spanning tree with maximum degree $O(B^*+\log{n})$ and cost $O(\opt_{B^*})$ where $\opt_{B^*}$ is the minimum cost of any spanning whose maximum degree is at most $B^*$. Our algorithm uses ideas from Lagrangean duality in a novel way. We show how a set of optimum Lagrangean multipliers yields bounds on both degree and cost of the computed solution.
TITLE: Integrating Constraint Propagation and Linear Programming, and Mixed Global Constraints and Inference in Hybrid CLP--IP Solvers.
SPEAKER: Erlendur S. Thorsteinsson.
WHEN: November 16th, 4:30-6:00pm.
WHERE: Porter Hall A19.
PAPERS: The complementing strengths of Constraint (Logic) Programming (CLP) and Mixed Integer Programming (IP) have recently received significant attention. Although various optimization and constraint programming packages at a first glance seem to support mixed models, the modeling and solution techniques encapsulated are still rudimentary. Apart from exchanging bounds for variables and objective, little is known of what constitutes a good hybrid model and how a hybrid solver can utilize the complementary strengths of inference and relaxations. This paper adds to the field by identifying constraints as the essential link between CLP and IP and introduces an algorithm for bidirectional inference through these constraints. Together with new search strategies for hybrid solvers and cut-generating mixed global constraints, solution speed is improved over both traditional IP codes and newer mixed solvers.

This is joint work with John Hooker and Greger Ottosson.

TITLE: On the Cycle Polytope of a Directed Graph.
SPEAKER: Egon Balas.
WHEN: November 23rd, 4:30-6:00pm.
WHERE: Porter Hall A19.

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.

TITLE: On the Crossing Number of Complete and Complete Bipartite Graphs.
SPEAKER: John F. Mackey, Department of Mathematics, Dartmouth College.
WHEN: February 8th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: Minimally Imperfect Graphs.
SPEAKER: Gerard P. Cornuéjols.
WHEN: February 15th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: A Relax and Cut Algorithm for the Quadratic Knapsack Problem.
SPEAKER: Marcio de Moraes Palmeira.
WHEN: February 29th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: Measures on Hereditary Properties of Graphs: Hierarchy and Structure.
SPEAKER: David Weinreich, University of Memphis.
WHEN: March 7th, 4:30-6:00pm.
WHERE: Wean 8427.
PAPERS: A {\em hereditary property} of graphs is a collection of labeled graphs closed under isomorphism and under taking induced subgraphs. Given a property $\mathcal{P}$, the {\em speed} of the property is $|\mathcal{P}^n|$, the number of labeled graphs on $n$ vertices in $\mathcal{P}$. In joint work with J\'ozsef Balogh and B\'ela Bollob\'as, we determined a hierarchy of speeds for hereditary properties, showing that there are jumps between allowable speeds. This hierarchy can be formulated in terms of the structures of graphs that occur in each level as well. In this talk, we shall discuss these results and directions for future work in this area, including a probabalistic formulation of the main questions.
TITLE: Relations between mixed 0/1 cuts.
SPEAKER: Michael Perregaard.
WHEN: March 28th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: Reconstructing strings from substrings.
SPEAKER: Bjarni V. Halldórsson.
WHEN: April 4th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.
PAPERS: Consider the following problem: Given an unknown string $s$ and the ability to ask queries of the type ``Is $x$ a substring of $s$?'', how may we take use of this to reconstruct $s$? This problem arizes in DNA sequencing. We will consider an algorithm by Pevzner and some recent work by Frieze and H.

If time allows we will consider other combinatorial problems arising in molecular biology.

TITLE: Variations on Nested Dissection.
SPEAKER: R. Ravi.
WHEN: April 11th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.
PAPERS: The order in which variables are eliminated in a Gaussian elimination procedure to solve a sparse symmetric linear system determines the extra space required for "fill-in" entries (non-zero values in previously zero locations in the sparse matrix arising from the pivots in the elimination).

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.

TITLE: Independent Sets in Random Graphs.
SPEAKER: Geoffrey Atkinson.
WHEN: April 18th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: Continuous Trajectories in Optimization Algorithms.
SPEAKER: Reha Tütüncü.
WHEN: April 25th, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.

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.

TITLE: Approximation Algorithms for the Weighted Edge-Dominating Set Problem and Some Variants.
SPEAKER: Ojas Parekh.
WHEN: May 2nd, 4:30-6:00pm.
WHERE: Tepper Cooper Auditorium.
PAPERS: Given a graph G and a cost function on its edges, the weighted edge-dominating set problem is that of finding a minimum cost set of edges, D such that each edge of G is either in D or is adjacent to some edge in D. The only previous result is a 4-approximation obtained by reducing the problem to an instance of weighted vertex cover. We use polyhedral scaling to provide an approximation guarantee of 2 1/10. We also show that the problem is as hard to approximate as the well-studied vertex cover problem, hence a constant factor less than 2 would be a tremendous result. If time permits we present approximation algorithms for the cases in which the edge-dominating set is constrained to be a tree or a tour.

Documents linked from this page can be read using PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.

Back to the ACO home page

esth@cmu.edu