Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!houxm!vax135!cornell!uw-beaver!tektronix!hplabs!sri-unix!YM@SU-AI.ARPA From: YM@SU-AI.ARPA Newsgroups: net.ai Subject: Seminars - Abstracts for BATS Message-ID: <13180@sri-arpa.UUCP> Date: Tue, 4-Sep-84 17:24:00 EDT Article-I.D.: sri-arpa.13180 Posted: Tue Sep 4 17:24:00 1984 Date-Received: Wed, 12-Sep-84 02:21:40 EDT Lines: 98 From: Yoni Malachi [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.