COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2005

Allocating bandwidth for communicating agents is a problem at the core of dimensioning a network to operate cost-effectively. Classical efficient algorithmic techniques such as shortest paths, network flows and linear programming have been the workhorses for solving the network routing models that arise in this context.

In order to be practically solvable, the models themselves drop many of the real-life side constraints. In this talk, we consider the impact of incorporating a variety of these constraints on fundamental combinatorial optimization problems. For the different versions, we also briefly describe recent telecommunication technologies which impose such constraints on traffic flow in a network.

Refreshments will be available immediately following the talk in the EOW Lounge, Room 330.

Shortest-path problems arise in a number of large-scale applications such as geographic information systems and web modelling. While shortest-path problems are well-studied in standard models of computation, they pose serious challenges if the graphs considered are too big to fit into main memory. When dealing with such massive data, it is important to optimize disk accesses rather than computation steps. In particular, locality of access is crucial, which is hard to achieve in graph algorithms in general and in shortest-path computations in particular. This talk gives an overview of the state of the art of algorithms for shortest-path type problems in massive graphs, discussing I/O-efficient and cache-oblivious algorithms for planar graphs and general undirected graphs. At the end of the talk, current challenges are discussed.

Consider a data space partitioned into cells together with a set of data points contained in this space. Our goal is to find the best piecewise-constant function (constant on the cells) that fits the data. In 1-dimensional space we might have a set of points representing the times that photons are emitted from a source of radiation from which we would like to obtain a graph of the intensity of the radiation. In 2-dimensional (or 3-dimensional) space we might have points representing the positions of galaxies and we would like to graph the density of the galaxies in the various regions of space.

For each partition of the data cells into blocks we have a piecewise-constant function and we would like to find the partition whose corresponding piecewise function has the highest value. We exhibit an O(N^2) dynamic programming algorithm for finding the optimal partition in a 1-dimensional data space. This algorithm can also be used to find the optimal partition of a higher dimensional data space if arbitrary blocks are allowed (not necessarily connected). We exhibit a branch and bound algorithm for finding the optimal partition in a higher dimensional data space if blocks are required to be connected. We don't yet know if this last problem is NP-complete.

Distance in graphs is a well-studied area with many practical applications. This talk will introduce two distance-based graph parameters: the influence number and the total influence number. Both of these parameters are new to the literature and are based on applications in psychology that deal with social networks. The influence number uses a set S which maximizes the sum of 1/2^d(u,S) for every vertex u not in S. The total influence number extends this idea to maximize the sum of 1/2^d(u,v) for every vertex u not in S and every vertex v in S. This talk will explore these two parameters, including how to find such a set on various classes of graphs and some complexity results.

The information presented is a result of work by myself, Steve Hedetniemi, Renu Laskar, and Jeremy Lyle from Clemson University, as well as Ulrike Stege and Iris van Rooij from the University of Victoria.

The hard-core lattice gas model is a weighted independent set model which received much attention in the communication networks, theoretical computer science, and statistical physics communities. The standard issue here is in deciding whether the influence of a boundary condition of a large graph is felt at the center of the graph. Connections to mixing rates of Markov chains, information propagation in regular trees and other subtopics make this research area rich and exciting to study. The speaker will attempt to survey various recent developments in this topic, including some of his own contribution. (No prior background in the topic will be assumed.)

Refreshments will be provided immediately following the talk in the EOW 330.