Abstracts

Mathematics in Theoretical Computer Science: Some Illustrative Examples

We will give three examples of how known theorems in the math literature have helped computer scientists. Our examples are:

a) An application of finite fields to Communication Complexity

b) An application of probability to sorting

c) An application of the Graph Minor Theorem to Algorithms.

This list is NOT exhaustive.

Dynamic Pricing and Renegotiation for Network Management

One way to manage network traffic is to allow bandwidth requests to closely track with application, such as browser needs and explicit user requests along with providing the ability to charge for more capacity. From the network management's perspective, it is advantageous to increase the charge when the demand is high (say premium charge during peak hours) and decrease the charge when the demand is low. Due to bursty nature of the traffic, it is hard to statically fix peak and non-peak hours. Instead, it is advantageous to allow the network to dynamically change the tariff parameters of the charging scheme.

This is called dynamic pricing scheme. How can a user survive such a scheme?

We will present simple online algorithms to renegotiate bandwidth dynamically.

This is a joint work with Mahe Velauthapillai (at Georgetown Univ.) and John Waclawski (at Cisco). Paper work for two patents is pending at Cisco.

Simultaneous Diophantine Approximation and linearization of C^2 map

The solution of a famous problem of dynamical systems theory (the question of the linearizability of holomorphic maps of the complex plane in the neighbourhood of a fixed point) turned out to involve number theory in an essential and intriguing way. Much less is known about the higher-dimensional case of this problem, and progress seems to depend on questions of ALGORITHM DESIGN for simultaneous approximation of sets of irrationals.

I will attempt to give a general survey and point out the links between the pure mathematics and computer science involved in attacks on this problem.

The K-Median Problem!

The k-median problem is one of the most well-studied clustering problems, i.e., those problems in which the aim is to partition a given set of points into clusters so that the points within a cluster are relatively close with respect to some measure. For metric k-median problem, we are given n points in a metric space. We select k of these to be cluster centers, and then assign each point to its closest selected center. If point j is assigned to center i, the cost incurred is propotional to the distance between i and j. The goal is to select k centers that would minimize the sum of the assignment costs.

In this talk I would present some recent results on the k-median problem.

Coping with Intractability: Approximation Algorithms

Since the development of the theory of NP-completeness in the early 70's, thousands of papers have appeared proving that various optimization problems are NP-hard. However, most of these papers do not suggest ways of coping with the intractability of optimization problems.

Approximation algorithms are essentially heuristics with a guaranteed performance behaviour. In the first part of the talk I will outline the major goals and objectives of this research area, and will give a flavour of the kinds of results that we will discuss in a full course (CMSC 858K) this spring. In the second part of the talk, I will describe some advances on optimization problems arising in multimedia data storage and data placement. I will also allude to several interesting problems that we are currently interested in related to the movement of multimedia data.

No technical background will be expected beyond knowledge of CMSC 251.

Locating Points in the Average Case: Fast and Simple

Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be computed efficiently. This problem has been heavily studied from the perspective of worst-case complexity, and many asymptotically optimal algorithms are known.

Suppose that for each cell z in the subdivision, the probability that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. This problem has been considered before, but existing data structures are quite complicated. We show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.