YM@SU-AI.ARPA (09/05/84)
From: Yoni Malachi <YM@SU-AI.ARPA>
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
The next Bay Area Theory Seminar (aka BATS) will be at Stanford, this Friday,
7 September.
The talks (and lunch) will take place in Room 200-305. This is a room on the
third floor of History Corner, the NE corner of the Stanford Campus Quadrangle.
The schedule:
10:00am U. Vazirani (Berkeley):
"2-Processor Scheduling in Random NC"
11:00am R. Anderson (Stanford):
"A P-complete Problem and Approximations to It"
noon: Lunch
1:00pm E. Lawler (Berkeley):
"The Traveling Salesman Problem Made Easy"
2:00pm A. Schoenhage (Tuebingen, IBM San Jose):
"Efficient Diophantine Approximation"
*****************************************************************************
ABSTRACTS:
10:00am: U. Vazirani:
"2-Processor Scheduling in Random NC"
(joint work with D. Kozen and V. Vazirani)
The Two-Processor Scheduling Problem is a classical problem in Computational
Combinatorics, and several efficient algorithms have been designed for it.
However, these algorithms are inherently sequential in nature. We give a
randomizing poly-log time parallel algorithm (run on a polynomial number of
processors). Interestingly enough, our algorithm for this purely
combinatoric-looking problem draws on some powerful algebriac methods. The
Two-processor Scheduling problem can be stated as follows:
Given a set S of unit time jobs, and a partial order specifying precedence
constraints among them, find an optimal schedule for the jobs on two identical
processors.
11:00am: R. Anderson (Stanford):
"A P-complete Problem and Approximations to It"
The P-complete problem that we will consider is the High Degree
Subgraph Problem. This problem is: given a graph G=(V,E) and an integer k,
find the maximum induced subgraph of G that has all nodes of degree at least
k. After showing that this problem is P-complete, we will discuss two
approaches to finding approximate solutions to it in NC. We will give a
variant of the problem that is also P-complete that can be approximated to
within a factor of c in NC, for any c < 1/2, but cannot be approximated by a
factor of better than 1/2 unless P=NC. We will also give an algorithm that
finds a subgraph with moderately high minimum degree. This algorithm exhibits
an interesting relationship between its performance and the time it takes.
1:00pm: E. Lawler (Berkeley):
"The Traveling Salesman Problem Made Easy"
Despite the general pessimism resulting from both theory and
practice, the TSP is not necessarily a hard problem--there are many
interesting and useful special cases that can be solved efficiently.
For example, there is an efficient procedure for finding an optimal
solution for the bottleneck TSP in the case that the distance matrix
is "graded." This result will be used to show how to solve a problem
of great practical importance to paperhangers: how to cut sheets from
a long roll of paper so as to minimize intersheet wastage.
Material for this talk is drawn from a chapter, by P. Gilmore,
E.L. Lawler, and D.B. Shmoys, of a forthcoming book, The Traveling
Salesman Problem, edited by Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan,
and D.B. Shmoys to be published by J. Wiley in mid-1985.
2:00pm: A. Schoenhage (Tuebingen, IBM San Jose):
"Efficient Diophantine Approximation"
Abstract: Given (a_1,...,a_n) in R^d (with d < n) and epsilon > 0, how to find
a nontrivial x = (x_1,...,x_n) in Z^n of minimal Euclidean norm nu such that
|x_1 a_1 + ... + x_n a_n| < epsilon holds. A weak version of this classical
task (where epsilon and nu may be multiplied by 2^(cn) ) can be solved in time
O(n^2 (d*n/(n-d) * log(1/epsilon))^(2+o(1))).
The main tool is an improved basis reduction algorithm for integer lattices.