INVITED SPEAKERS


Uri Feige
 

Christos Papadimitriou
 

Madhu Sudan
 
 

Avi Wigderson
 
 
 

MINISYMPOSIUM ON SCHEDULING


Organizer:   Klaus Jansen
 

 Speakers:
 

                         Susanne Albers
 

                          Evripidis Bampis
 

                           Stefano Leonardi
 
 

ACCEPTED PAPERS

 

 
 
 
 
 
 
 
 
 

RANDOM:

 

 
 
 
 
 
 
 
 
 

TITLE: Testing the Diameter of Graphs
AUTHORS: Michal Parnas and Dana Ron
 

TITLE: Improved derandomization of BPP using a hitting set generator.
AUTHORS: Oded Goldreich and Avi Wigderson.
 

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

TITLE: Completeness and robustness properties of min-wise
independent permutations
AUTHORS: Andrei Broder and Michael Mitzenmacher
 

TITLE:  Discrepant Sets Yield Approximate Min-Wise Independent Permutation
AUTHORS: Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman
 

TITLE: Algorithms for Graph Partitioning on the Planted Partition Model
AUTHORS: Anne E. Condon and Richard M. Karp
 

TITLE: Pfaffian Algorithms for Sampling Routings on Regions with
Free Boundary Conditions
AUTHOR: Russell Martin and Dana Randall
 

TITLE: "Improved Testing Algorithms for Monotonicity"
AUTHORS: Yevgeniy Dodis, Oded Goldreich, Eric Lehman,
Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky
 

TITLE: Linear Consistency Testing
AUTHORS: Yonatan Aumann, Michael O. Rabin and Madhu Sudan
 

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

TITLE: Fast Approximate PCPs for Multidimensional Bin-packing Problems
AUTHORS: Tugkan Batu, Ronitt Rubinfeld, Patrick White

TITLE: Improved Bounds for Sampling Contigency Tables
AUTHOR: Benjamin James Morris
 
 
 
 

APPROX:

 

 
 
 
 
 
 
 
 
 

TITLE: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
AUTHOR: Hans Kellerer
 

TITLE: Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths
AUTHORS: Noga Alon, Uri Arad, Yossi Azar
 

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

TITLE: Scheduling with Machine Cost
AUTHORS: Csan\'ad Imreh and John Noga
 

TITLE: Efficient Redundant Assignments under Fault-Tolerance Constraints
AUTHORS: Dimitris Fotakis and Paul Spirakis
 

TITLE: Approximating Minimum Manhattan Networks
AUTHORS: Joachim Gudmundsson, Christos Levcopoulos and Giri Narasimhan
 

TITLE: Approximation of Multi-Color Discrepancy
AUTHORS: Benjamin Doerr, Anand Srivastav
 

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

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

TITLE: A New Approximation Algorithm for the Demand Routing and Slotting Problem
with Unit Demands on Rings
AUTHOR: Christine Cheng
 

TITLE: Set Cover with Requirements and Costs Evolving over Time
AUTHORS: Milena Mihail
 

TITLE: Multi-coloring Planar graphs and Partial k-Trees
AUTHORS: Magnus M Halldorsson and Guy Kortsarz