Speaker: Hubert Chan
Time: Wednesday 12-1pm
LOCATION: NSH 3305
Title: Sparse Spanners for Doubling Metrics
Abstract:
Graph spanners have applications in communication networks, distributed computing and computational geometry. We motivate our problem by considering the following application in wireless networks. Suppose we have a set of nodes representing wireless access points. Data packets can be sent from one node to another directly if the two nodes are directly connected via a dedicated frequency. Otherwise, data packets have to travel through intermediate nodes from the source to the destination. Every pair of nodes (x,y) has some distance d(x,y), which represents the time to send a data packet between the nodes x and y if there is a direct connection between them. The goal is to construct a network by assigning a small number of dedicated frequencies for directly connected pairs (which form a sparse spanner) such that for every pair of nodes (u,v), the time to send a data packet between them is at most some small multiplicative factor (typically less than 1.5) of d(u,v). We show that if the distance function obeys some bounded growth property (namely, induces a doubling metric), then it is possible to construct such a network with a linear number of direct connections. The bounded growth property is general enough to include many common distance functions, such as constant dimensional Euclidean distances. We also show that the network has additional nice properties, such as each node having a constant number of connections. Moreover, if we allow the number of connections to be nearly linear $O(n log^* n)$, then for every pair of nodes, there is a short path between them that uses only a constant number of intermediate nodes. This is useful when congestion and latency are taken into account. This is joint work with Anupam Gupta.
TITLE: Approximating k-MultiCut Problem
SPEAKER: Mohit Singh
WHEN: December 8, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Given an undirected graph, a set of $t$ pairs of vertices, the multi-cut problem is to find the minimum set of edges to remove which separate all pairs. The $k$-multicut problem is a generalization of the multicut problem in which one is given a target $k \leq t$ and asked to remove only $k$ pairs. We use techiniques from combinatorial optimization: Lagrangian relaxation and Total unimodularity, to obtain constant factor approximation for the $k$-multicut problem on trees. This also leads to $O(log^2 n log logn)$-approximation for the $k$-multicut problem on general graphs, where $n$ is the number of vertices in the graph. We also give bicriterion approximation algorithm for the $k$-multicut problem. Our techniques also give a simple $2$-approximation algorithm for the multicut problem on trees matching the best known algorithm of Garg, Vazirani and Yannakakis’94.
Joint Work with Viswanath Nagarajan and Daniel Golovin. To appear in SODA’06.
Friday, December 9, 2005
1:30 p.m. Posner Hall 151
Francois Margot
Associate Professor of Operations Research, Tepper School of Business
Code Construction with ILP
This talk covers on-going work to solve one of the oldest and most famous problems in combinatorial coding theory, the Football Pool Problem. A more technical description of the problem is finding a ternary code of minimum cardinality with covering radius one. The smallest open case, for code words of length 6, still resists all solution attempts, despite a lot of efforts.
The talk covers techniques proposed by others and their integration within several ILP formulations used as preliminary steps in a solution approach. Partial results obtained are promising and improving the best known lower bound on the solution seems possible.
Improving the formulation of the ILPs is an open research problem that has received little attention so far. Some research directions will be mentioned.
The solution of the ILPs (binary and non binary) uses isomorphism pruning techniques to good effect. Yet, extensive computing resources will be required for a complete solution. Code using Condor and MW giving access to large parallel grid computing has been implemented.
