|
Capital Area Theory Seminar: Fall 2002 |
The Capital Area Theory Symposia is an UMIACS sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department.
CATS will usually meet on Friday's, at 1:00pm in CSIC 3118, but some talks may be at a different place and time. Abstracts are available.
We are given a set of points p_1,\ldots, p_n and a symmetric distance matrix (d_ij ) giving the distance between p_i and p_j . We wish to construct a tour that minimizes \sum_{i=1}^n l(i) where l(i) is the latency of p_i , defined to be the distance traveled before first visiting p_i. This problem is also known in the literature as the deliveryman problem or the traveling repairman problem.
It arises in a number of applications including disk-head scheduling, and turns out to be surprisingly different from the traveling salesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.
The purpose of this talk is to convey three approaches to a typical problem -- pattern matching, and its extensions.
The basic problem is that given an alphabet, say \sigma = {H,T}, a pattern B \in \sigma^{+}, say B=HTH, a random process (say toss a coin of Head and Tail) that generates strings \subset \sigma^{+}. The question is that what is the expected value of the first time to obtain B in the random process.
Based on the basic problem, we extend it to that given two patterns A and B, assume that A does not contain B, what is the expected value of the first time to reach B starting with pattern A.
Three approaches will be given to obtain the same results. The first approach explores the "fairness" property a Martingale process; the second one utilizes absorbing Markov chains; the third one is an elegant combinatorial approach.
NOTE that NO prerequisite knowledge about Martingale or Markov chains are assumed in order to attend the talk.
Based on the above results, we will examine a game called "Penney-ante": two players, the first one picks a pattern A of H's and T's, and then the second one knowing the choice of the first player, picks a different pattern B. Assume that A and B don't contain each other. A coin is tossed a sequence of times, and the player whose pattern comes up first is the winner. We will see that the odds that the first player will win are given by the John conway's formula. We will also see that when the length of patterns is 2, this is a fair game, but if it is 3, the second player has an advantage no matter what choice the first player makes...
In this review lecture, we first discuss how to reduce the problems of robot motion planning to the problems of computing paths inside polygons with or without holes. Then we discuss the algorithms for computing geometric shortest paths and minimum link paths inside a polygon using visibility structure of the polygon. In this context, we also discuss curvature-constrained shortest path problem. Finally, we discuss the problems of exploring an unknown polygon using both continuous and discrete visibility, and present a few approximation on-line algorithms. We summarize the discussion by suggesting a few open problems.
The talk presents approximation algorithms with tight performance bounds for an optimization problem that arises in the context of data placement in multimedia storage systems.
We are given a collection of M multimedia objects (data items) that need to be assigned to a storage system consisting of N disks d_1,d_2,...,d_N. We are also given sets U_1,U_2,...,U_M such that U_i is the set of clients seeking the i-th data item. Data item i has size s_i. Each disk d_j is characterized by two parameters, namely, its storage capacity C_j which indicates the maximum total size of data items that may be assigned to it, and a load capacity L_j which indicates the maximum number of clients that it can serve. The goal is to find a placement of data items to disks and an assignment of clients to disks so as to maximize the total number of clients served, subject to the capacity constraints of the storage system.
The talk presents the first successful attempt at removing the assumption that all data items have the same size. For the case where s_i in {a_1,...,a_c} for some constant c and when k is a fixed constant (a_i >= 1), we develop a polynomial time approximation scheme (PTAS). For arbitrary k, the talk presents algorithms with tight bounds when s_i in {1,2}. In particular we can show that a constant fraction of all clients can be assigned, regardless of the input distribution. By combining the above methods, for arbitrary k, when s_i in {1,2} we obtain a polynomial time approximation scheme (PTAS).
This is a joint work with Samir Khuller.
We are given a bipartite graph G(A,B,E) with bipartition (A,B). We are also given a value x_ij for each edge (i,j) in E. We are interested in a randomized polynomial-time scheme that rounds each x_ij to a random variable X_ij in {0,1}, in such a way that the following properties hold:
We present the COST-DISTANCE problem: find a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(log k) randomized approximation scheme for COST-DISTANCE, where k is the number of sources. We reduce many common network design problems to COST-DISTANCE, obtaining (in some cases) the first known logarithmic approximation for them. These problems include single-sink buy-at-bulk with variable pipe types between different sets of nodes, and facility location with buy-at-bulk type costs on edges. Our algorithm is also the algorithm of choice for several previous network design problems, due to its ease of implementation and fast running time.
Consider the following function:
x is a string of length n
y_1, y_2 \in {1,...,n} which we represent in base 2. Think of y_1, y_2 as a string of length log n. Let y_1 XOR y_2 be the string you get by doing the bitwise XOR of y_1 and y_2, and interpret as a number in {1,...,n}
GIVEN x, y_1, y_2
GAF(x,y_1,y_2) is the (y_1 XOR y_2) th bit of x.
(for example, if y_1= 17 = 10001 and y_2 = 7=00111
then y_1 XOR y_2 is
(1 xor 0)(0 xor 0)(0 xor 1)(0 xor 1)(1 xor 1)=10110 = 22)
Alice has y_1,y_2
Bob has x, y_1
Carol has x, y_2
Alice, Bob, and Carol do not talk to each other. Alice, Bob, and Carol are going to communicate to THE MAN by sending him a string of bits.
HOW MANY BITS DO THEY HAVE TO SEND SO THAT THE MAN CAN COMPUTE GAF(x,y_1,y_2) ?
SURPSING UPPER BOUND: There is a protocol where Alice will send y_1 and y_2 (2log n, no surprise), Bob and Carol each send a message of length n^{0.93} bits.
EASY UPPER BOUND: There is an easy proof of an lower bound of sqrt(n)/2. (The result was known, the proof is NEW and due to BILL GASARCH!)
In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. Within a round, they may also wait to see the inputs of the good players. A protocol is called resilient if a good leader is elected with probability bounded away from 0.
We give a simple, constructive leader election protocol that is resilient against coalitions of size bn, for any b<1/2. Our protocol takes log* n + O(1) rounds, each player sending at most log n bits per round. For any constant k, our protocol can be modified to take k rounds and be resilient against coalitions of size en/(log^{(k)} n)^3, where e is a small enough constant and log^{(k)} denotes the logarithm iterated k times. This is constructive for k>=3.