Tentative Program Random-Approx 99

Soda Hall - room 306

Computer Science Department

University of California Berkeley

Sunday 6:00pm - 9:00 pm   - August 8th, 1999:  Welcome reception

 Wells Fargo Room - Haas School of Business

Monday - August 9th, 1999

Registration Starts at 12:00pm

1:30pm : Invited Talk

Proteins and Algorithms
Christos Papadimitriou

Session: Random 1

2:20pm:  Completeness and robustness properties of min-wise
independent permutations
Andrei Broder and Michael Mitzenmacher

2:45pm:  Low-Discrepancy Sets Yield Approximate Min-Wise
Independent Permutation Families
Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman

3:10pm: Coffee Break

Session: Approx 1

3:30pm: Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths
Noga Alon, Uri Arad, Yossi Azar

3:55pm:  Approximating Minimum Manhattan Networks
Joachim Gudmundsson, Christos Levcopoulos and Giri Narasimhan

4:20pm: Approximation of Multi-Color Discrepancy
Benjamin Doerr, Anand Srivastav

4:55pm: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
Hans Kellerer

Tuesday - August 10th, 1999


8:30am: Invited Talk

Information-theoretic notions in computational complexity
Madhu Sudan

Session: Approx 2

9:20am: Set Cover with Requirements and Costs Evolving over Time
Milena Mihail

9:45am: Multi-coloring Planar graphs and Partial k-Trees
Magnus M Halldorsson and Guy Kortsarz

10:05am: Coffee Break

Session: Random 2

10:25am: Testing the Diameter of Graphs
Michal Parnas and Dana Ron

10:50am: Improved Testing Algorithms for Monotonicity
Yevgeniy Dodis, Oded Goldreich, Eric Lehman,
Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky

11:15am: Linear Consistency Testing
Yonatan Aumann,  Johan Haastad, Michael O. Rabin and Madhu Sudan

11:40am:  A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum
Spanning Forest
Seth Pettie and Vijaya Ramachandran

Lunch Break

1:30 am: Invited Talk

Probabilistic and Deterministic Approximations of the Permanent
Avi Wigderson

Session: Random 3

2:20pm: Improved derandomization of BPP using a hitting set generator.
Oded Goldreich and Avi Wigderson.

2:45pm: Probablistic Construction of Small Strongly
Sum-Free Sets via Large Sidon Sets
Andreas Baltz, Tomasz Schoen, Anand Srivastav

3:10pm: Coffee Break

Session: Approx 3

3:30pm:   Stochastic Machine Scheduling:
Performance Guarantees for LP-based Priority Policies
Rolf H. Moehring, Andreas S. Schulz, and Marc Uetz

3:55pm:  Efficient Redundant Assignments under Fault-Tolerance Constraints
Dimitris Fotakis and Paul Spirakis

4:20pm:  Scheduling with Machine Cost
Csanad Imreh and John Noga

4:55pm: A linear time approximation scheme for the job shop scheduling problem.
Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko

6:30 pm: Banquet: Women Faculty Club



Wednesday - August 11th, 1999



Organizer:    Klaus Jansen


Susanne Albers:  Scheduling with unexpected machine breakdowns

Evripidis Bampis: Approximation algorithms for minimizing the weighted
sum of completion times

Stefano Leonardi: Scheduling to optimize flow time

Lunch Break

1:30pm: Invited Talk

Randomized rounding of semidefinite programs - variations on the MAX CUT example
Uri Feige

Session: Approx 4

2:20pm: Hardness Results for the Power Range Assignment
Problem in Packet Radio Networks
Andrea E. F. Clementi , Paolo Penna ,and Riccardo Silvestri

2:45pm: A New Approximation Algorithm for the Demand Routing and Slotting Problem
with Unit Demands on Rings
Christine Cheng

3:10pm: Coffee Break

Session: Random 4

3:30pm: Algorithms for Graph Partitioning on the Planted Partition Model
Anne E. Condon and Richard M. Karp

3:55pm:  Improved Bounds for Sampling Contingency Tables
Benjamin James Morris

4:20pm:  Fast Approximate PCPs for Multidimensional Bin-packing Problems
Tugkan Batu, Ronitt Rubinfeld, Patrick White

4:55am: Pfaffian Algorithms for Sampling Routings on Regions with
Free Boundary Conditions
Russell Martin and Dana Randall