ACO The ACO Seminar (Fall 2004).

All talks on a combinatorial/discrete math/theoretical CS/not so theoretical CS/OR theme are welcome!

If you want to be a speaker or have questions or suggestions about the seminar, please contact...
the organizers: Prasad Chebolu (pchebolu @ andrew . cmu . edu) and Cliff Smyth (csmyth @ andrew . cmu . edu).

The next speaker will be Colin Cooper on Thursday, April 28th 4:30-5:30 PM in WEH 6423 .

Past Schedule:

1995-96 1996-97 1998-99 1999-00 2000-01 2001-02 Fall 02 Spring 04

Current Schedule(2004-05):

TITLE: The diameter of randomly perturbed digraphs and some applications
SPEAKER: Abie Flaxman
WHEN: Tuesday, October 12, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)
PAPERS: The diameter of randomly perturbed digraphs and some applications

ABSTRACT: The central observation of this talk is that if \epsilon n random edges are added to any n node connected graph or digraph then the resulting graph has diameter O(log n) with high probability. We apply this to smoothed analysis of algorithms and property testing.

Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for graphs with bounded out-degree, it is NL-complete. By XORing an arbitrary bounded out-degree digraph with a sparse random digraph R = G(n,\epsilon n) we obtain a ``smoothed'' instance. We show that, with high probability, a log-space algorithm will correctly determine if a smoothed instance is strongly connected. The algorithm consists of, for every pair (s,t), checking if a series of random walks starting at s ever reaches t (and can be derandomized by carefully exploring vertices within a certain distance). We also show that if NL is not contained in L then no heuristic can recognize similarly perturbed instances of (s,t)-connectivity.

Property Testing: A digraph is called k-linked if for every choice of 2k distinct vertices s_1, ... ,s_k,t_1,... ,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r=1,... ,k. Recognizing k-linked> digraphs is NP-complete for k >= 2. We describe a polynomial time algorithm for bounded degree digraphs which accepts k-linked graphs with high probability, and rejects all graphs which are at least \epsilon n edges away from being k-linked. The algorithm consists of perturbing the graph by adding \epsilon n/2 random edges, and then for every choice of terminal pairs, checking if a series of vertex disjoint random walks starting from s_1, ... ,s_k ever reach t_1,....,t_k.

This is joint work with Alan Frieze.


TITLE: Multicommodity Flow with Holding Costs
SPEAKER: Barbara Anthony
WHEN: Tuesday, October 19, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)

ABSTRACT: Consider a directed network with edge capacities and per-unit-time holding costs at each node. We seek flows over time that drain all supplies to the sink, obey capacity constraints and minimize the total holding cost incurred. This problem is motivated by job-shop scheduling problems, whose relaxations can be viewed as continuous multicommodity flow problems with holding costs. We give new results about the structure of optimal solutions, in particular for acyclic graphs which capture the case of flexible flow shops. For acyclic graphs, we prove an O(mn) bound on the number of times flow changes can occur, and give a class of examples requiring \Omega(mn) flow changes, proving the bound is tight.

This is joint work with Lisa Fleischer, to be presented at INFORMS 2004.


TITLE: Hamilton Cycles in Random Lifts of Graphs
SPEAKER: Kelley Burgin
WHEN: Tuesday, October 26, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)

ABSTRACT: For a graph K, a random n-lift G of K has vertex set V(K)x[n] where for each vertex v\in V(K), {v}x[n] is called the pillar above v and will be denoted by p_v. The edge set of G is obtained by placing a random perfect matching between pillars p_u and p_w for each edge (u,w)\in E(K). We show that there exists a constant h_0 such that if h>h_0 then a random lift of the complete graph K_h is hamiltonian whp.

This is joint work with Prasad Chebolu, Colin Cooper, Alan Frieze.


TITLE: A geometric preferential attachment model of networks
SPEAKER: Juan Vera
WHEN: Tuesday, November 2, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)

ABSTRACT: We study a random graph $G_n$ that combines certain aspects of geometric random graphs and preferential attachment graphs. Vertices are chosen uniformly at random from the surface of the unit sphere. After generating a vertex, we randomly connect it to $m$ previously generated vertices from those which are within distance r. Neighbors are chosen with probability proportional to their current degree.

We show that if m and r are sufficiently large (will be made precise in the talk) this graph presents the following properties:
- Power law degree sequence.
- Small separators.
- O(m/r) diameter.

This is joint work with Abie Flaxman, Alan Frieze.


TITLE: Randomized Rounding for Spanning Trees
SPEAKER: Mohit Singh
WHEN: Tuesday, November 23, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)

ABSTRACT: In this talk we will discuss the randomized rounding method for constrained and bicriterion spanning tree problems. We will present how a result by Alon on Network Reliability can be adapted to obtain good approximation algorithms for spanning tree problems. We will obtain approximation guarantees for (at least)two different problems using the same technique.

Talk based on Noga Alon " A note on Network Reliability", Discrete Probability and Algorithms, vol 72,1995,11-14.

This is joint work with Kedar Dhamdhere and R. Ravi.


TITLE: Enumerating Brunnian Links
SPEAKER: Paul Gartside
WHEN: Tuesday, November 30, 12:30-1:30 PM
WHERE: OSC 200 (Old Student Center)

ABSTRACT: The Borromean Rings are a configuration of three rings which are linked together in such a way that no two rings are linked when the third ring is removed. A Brunnian $n$-link is the generalization to $n$ linked rings with the property that if any one ring is deleted then the remaining rings are completely unlinked. In this talk we will see how to classify and count Brunnian links (joint work with Sina Greenwood).

This is joint work with Sina Greenwood.


TITLE: Induced Cycles in Powers of Complete Graphs
SPEAKER: Jerzy Wojciechowski
WHEN: Thursday, February 3, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: Let Knd be the product of d copies of the complete graph Kn, n ≥ 2, d ≥ 2. It is convenient to think of the vertices of Knd as d-tuples of n-ary digits, that is, as the d-tuples of the elements of the set {0,1,...,n-1}, with edges between two d-tuples differing at exactly one coordinate. Let S(Knd) be the length of the longest induced cycle in Knd.

The problem of finding a good lower bound for the value of S(Knd) has a long history. It was first met by Kautz (1958 ) in the case of n = 2 ( known in the literature as the snake-in-the-box problem) in constructng a type of error-checking code for a certain analog-to- digital conversion systems. He showed that S(K2d) ≥ λ√2d, for some positive constant λ. Several authors improved the lower bound for S(K2d) until Evdokimov (1969) obtained a lower bound that is linear in 2d, that is, he showed that S(K2d) ≥ λ2d, where λ is a positive constant.

The general case of the problem, with an arbitrary value of n, was introduced by Abbott and Dierker (1977), and the bound S(Knd) ≥ λnnd was proved by Abbott and Katchalski (1991) in the case of even n and by Wojciechowski(1994) in the case of odd n. The constant λn obtained in these results is dependent on n and approaches 0 as n → ∞. Actually, a linear lower bound with the coefficient independent from both n and d is not possible since Abbott and Katchalski (1988) proved that S(Knd) ≤ (1 + 1/(d-1))n d-1.

A natural question is whether there is a positive constant λ, that is independent from both n and d, such that S(Knd) ≥ λnd-1.

In this talk we will show that the answer to that question is positive.


TITLE: The Effect of Network Topology on the Spread of Epidemics
SPEAKER: A. Ganesh
WHEN: Thursday, February 24, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We study the SIS epidemic model (or contact process) on graphs, and identify topological properties of the graph that determine the persistence of epidemics. We show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, then the mean epidemic lifetime is of order log n, where n is the number of nodes. Conversely, if this ratio is smaller than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order ena, for a positive constant a. We apply these results to the hypercube and the star topologies and also to Erdos-Renyi and power law random graphs.


TITLE: Permutation sum sets
SPEAKER: Cliff Smyth
WHEN: Thursday, March 3, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: A family of functions from an ableian group to itself is a permutation sum set if each function is a bijection and the pointwise sum of each pair of functions is a bijection. We study the maximum size of such sets for various abelian and non-abelian groups and draw a connection to certain families of Latin squares.

This is joint work with Don Coppersmith and Abie Flaxman.


TITLE: Restrictions on sums over Z
SPEAKER: Yiannis Koutis
WHEN: Thursday, March 17, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We study component-wise sums of vectors over Zpd. Let A be an arbitrary subset of Z2d, with |A| >2d. Let f(A,v) be the number of subsets of A, whose sum is v, and 0 denote the zero vector. What is the probability that f(A,0) is even? How big can the difference f(A,v)-f(A,0) be ? We answer these and a few other related questions, for any prime p. We also draw a connection to the Set Packing problem. Our main tool is the representation theory for Zpd.


TITLE: Lower-Stretch Spanning Trees
SPEAKER: Dan Spielman
WHEN: Thursday, March 24, 4:30-5:30 PM
WHERE: WEH 4623 (Wean Hall)

ABSTRACT: A low-stretch spanning tree T of a graph G is a spanning tree subgraph in which most edges of G can be routed with small dilation. In particular, the stretch of an edge of G in T is the length of the path in T connecting the endpoints of that edge. The average stretch is the average over edges in G of their stretch. In an analysis of an algorithm for the k-server problem, Alon, Karp, Peleg and West showed that there exist spanning trees of average stretch 2O(&radic n). We were motivated to improve their construction because this average-stretch is the dominant term in the complexity of a new solver for diagonally-dominant systems of equations. We present a O(m log2n)-time algorithm that constructs trees of much lower average stretch: O(log2 n log log n).

This is joint work with Michael Elkin, Yuval Emek and Shang-Hua Teng.


TITLE: A Gessel-Viennot-Type Method for Cycle Systems
SPEAKER: Christopher Hanusa
WHEN: Thursday, March 31, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: In the 1980's, Gessel and Viennot presented a determinantal method for counting non-intersecting lattice paths. We present an extension of this method to counting non-intersecting cycle systems in a particular type of graph we call a hamburger. This ``Hamburger Theorem'' gives a purely combinatorial proof of a determinantal formula for the number of domino tilings of an Aztec diamond, as first introduced by Brualdi and Kirkland in 2003. We present this argument and expand upon the Hamburger Theorem's applications to domino tilings of other regions of interest.


TITLE: Sparsest Cut Problems and Embeddings into L1
SPEAKER: Anupam Gupta
WHEN: Thursday, April 7, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We will talk about two problems: (a) that of finding good embeddings of finite metric spaces into L1, the "Manhattan" metric and (b) finding cuts in graphs with small conductance. We will show that the two problems are closely related to each other, and how recent results for the former give us approximation algorithms for the latter.

As a corollary of our results, we show the following basic fact about metric spaces: any n-point subset of L1 can be mapped into Euclidean space so that the distances are distorted by at most a multiplicative factor of O(log3/4 n), thus improving on a previous O(log n) bound of Bourgain (1986).

The talk is partly based on results with Shuchi Chawla and Harald Raecke, and will be self contained.


TITLE: Random 2-SAT Does not depend on a giant
SPEAKER: David Kravitz
WHEN: Thursday, April 14, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: Here we introduce a new model for random 2-SAT. It is well-known that on the standard model there is a sharp phase transition, the probability of satisfiability quickly drops as the number of clauses exceeds the number of variables. The location of this phase transition suggests that there is a direct connection between the appearance of a giant in the corresponding 2n-vertex graph and satisfiability. Here we show that the giant has nothing to do with satisfiability, and in fact the expected degree of a randomly chosen vertex is the important thing.


TITLE: On the Average Case Performance of Some Greedy Approximation Algorithms for the Uncapacitated Facility Location Problem
SPEAKER: Abie Flaxman
WHEN: Thursday, April 21, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees.

We analyze the performance of three related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these three algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.


TITLE: The cover time of random walks on random graphs
SPEAKER: Colin Cooper
WHEN: Thursday, April 28, 4:30-5:30 PM
WHERE: WEH 6423 (Wean Hall)

ABSTRACT: We discuss several results related to the time taken for a random walk to visit all vertices of a graph, the cover time. We first discuss this in relation to two classical models of random graphs viz. $G_{n,p}$ and random $r$-regular graphs. We then consider the preferential attachment graph. We give high probability, asymptotically precise estimates for the cover time in all cases.


PostScript Ghostview or GSview, Adobe Acrobat Reader, Sun StarOffice Impress or Microsoft PowerPoint Viewer.

Back to the ACO home page

pchebolu @ andrew . cmu . edu