Title: Infrastructure Leasing Problems
Speaker: Barbara Anthony
When: Friday, October 5, 10:30 AM
Where: Doherty 4303
Abstract:
Consider the following Steiner Tree leasing problem. Given a graph G = (V,E) with root r, and a sequence of terminal sets D_t subset of V for each day t in [T]. A feasible solution to the problem is a set of edges E_t for each t connecting D_t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we lease edges for say, {a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of
time. What is a good leasing strategy? We give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
This proposal includes joint work with Anupam Gupta.
Committee: Anupam Gupta (Chair), Tom Bohman, Alan Frieze, R. Ravi
Who: Amin Coja-Oghlan
Where: NSH 1507
When: Noon, 2007-10-03
Title: The solution space geometry of random constraint satisfaction problems
Abstract:
Random instances of constraint satisfaction problems such as k-SAT or k-Coloring are notoriously hard for many algorithmic techniques, in particular if the density of the instance is close to the threshold for the existence of a solution. Recent non-rigorous work from the statistical physics community has led to new algorithms (e.g., “Survey Propagation”) that perform emprically very well on random instances. These algorithms are based on hypotheses about the “solution space geometry” of random constraint satifaction problems, i.e., the number and relative location of the solutions. In this talk I will discuss these hypotheses as well as their algorithmic implications, and present some recent mathematically rigorous work on proving some of the hypotheses. Parts of the talk are based on joint work with Dimitris Achlioptas and Alan Frieze.
Title: Eigenvalues and discrepancy
Speaker: Amin Coja-Oghlan (Humboldt University, Berlin)
When: October 4, 16:30-17:30pm
Where: Wean Hall 5302
Abstract:
A graph G has “low discrepancy” if the global distribution of the edges of G resembles the edge distribution of a random graph of the same density. Moreover, G has a “large spectral gap” if the second largest eigenvalue of the adjacency matrix of G (or another suitable matrix representation of G) is significantly smaller than the average degree. It is well known (and easy to see) that a graph with a large spectral gap has low discrepancy. In this talk I will investigate the converse implication in the case of sparse graphs. The main result is that low discrepancy implies that G “essentially” has a large spectral gap. The talk is based on a joint paper with Noga Alon, Hiep Han, Mihyun Kang, Vojtech Rodl, and Mathias Schacht.
