Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques: Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX’99, Berkeley, CA, USA, August 8-11, 1999.

Andrei Z. Broder, Michael Mitzenmacher (auth.), Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair (eds.)3540663290, 9783540663294

This book constitutes the refereed proceedings of the Third International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM’99, held jointly with the Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX’99, in Berkeley, California in August 1999.
The volume presents 24 revised full papers selected from 44 submissions and four invited contributions. The papers present a wealth of new results and document the state-of-the-art in the areas covered by the workshop.

---

Table of contents :
Front Matter….Pages –
Completeness and Robustness Properties of Min-Wise Independent Permutations….Pages 1-10
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families….Pages 11-15
Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths….Pages 16-27
Approximating Minimum Manhattan Networks….Pages 28-38
Approximation of Multi-Color Discrepancy….Pages 39-50
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem….Pages 51-62
Set Cover with Requirements and Costs Evolving over Time….Pages 63-72
Multicoloring Planar Graphs and Partial  k -Trees….Pages 73-84
Testing the Diameter of Graphs….Pages 85-96
Improved Testing Algorithms for Monotonicity….Pages 97-108
Linear Consistency Testing….Pages 109-120
Improved Bounds for Sampling Contingency Tables….Pages 121-129
Probabilistic and Deterministic Approximations of the Permanent….Pages 130-130
Improved Derandomization of BPP Using a Hitting Set Generator….Pages 131-137
Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets….Pages 138-143
Stochastic Machine Scheduling: Performance Guarantees for LP-Based Priority Policies….Pages 144-155
Efficient Redundant Assignments under Fault-Tolerance Constraints….Pages 156-167
Scheduling with Machine Cost….Pages 168-176
A Linear Time Approximation Scheme for the Job Shop Scheduling Problem….Pages 177-188
Randomized Rounding for Semidefinite Programs – Variations on the MAX CUT Example….Pages 189-196
Hardness Results for the Power Range Assignment Problem in Packet Radio Networks….Pages 197-208
A New Approximation Algorithm for the Demand Routing and Slotting Problem with Unit Demands on Rings….Pages 209-220
Algorithms for Graph Partitioning on the Planted Partition Model….Pages 221-232
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest….Pages 233-244
Fast Approximate PCPs for Multidimensional Bin-Packing Problems….Pages 245-256
Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions….Pages 257-268
Scheduling with Unexpected Machine Breakdowns….Pages 269-280
Scheduling on a Constant Number of Machines….Pages 281-287
Back Matter….Pages –