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 Pro / edited by Dorit Hochbaum, Klaus Jansen, Jose D.P. Rolim, Alistair Sinclair.

Format:

Book

Contributor:

Hochbaum, Dorit, editor.

Jansen, Klaus, editor.

Rolim, José D. P., editor.

Sinclair, Alistair, 1960- editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 1671.

Lecture Notes in Computer Science, 0302-9743 ; 1671

Language:

English

Subjects (All):

Computer programming.

Probabilities.

Data structures (Computer science).

Algorithms.

Computer science--Mathematics.

Computer science.

Programming Techniques.

Probability Theory and Stochastic Processes.

Data Structures and Information Theory.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Data Structures.

Local Subjects:

Programming Techniques.

Probability Theory and Stochastic Processes.

Data Structures and Information Theory.

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Data Structures.

Physical Description:

1 online resource (X, 298 pages).

Edition:

First edition 1999.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1999.

System Details:

text file PDF

Contents:

Session Random 1

Completeness and Robustness Properties of Min-Wise Independent Permutations

Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families

Session Approx 1

Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths

Approximating Minimum Manhattan Networks

Approximation of Multi-Color Discrepancy

A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

Session Approx 2

Set Cover with Requirements and Costs Evolving over Time

Multicoloring Planar Graphs and Partial k-Trees

Session: Random 2

Testing the Diameter of Graphs

Improved Testing Algorithms for Monotonicity

Linear Consistency Testing

Improved Bounds for Sampling Contingency Tables

Invited Talk

Probabilistic and Deterministic Approximations of the Permanent

Session Random 3

Improved Derandomization of BPP Using a Hitting Set Generator

Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets

Session Approx 3

Stochastic Machine Scheduling: Performance Guarantees for LP-Based Priority Policies

Efficient Redundant Assignments under Fault-Tolerance Constraints

Scheduling with Machine Cost

A Linear Time Approximation Scheme for the Job Shop Scheduling Problem

Randomized Rounding for Semidefinite Programs - Variations on the MAX CUT Example

Session Approx 4

Hardness Results for the Power Range Assignment Problem in Packet Radio Networks

A New Approximation Algorithm for the Demand Routing and Slotting Problem with Unit Demands on Rings

Session Random 4

Algorithms for Graph Partitioning on the Planted Partition Model

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

Fast Approximate PCPs for Multidimensional Bin-Packing Problems

Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions

Minisymposium on Scheduling Talks

Scheduling with Unexpected Machine Breakdowns

Scheduling on a Constant Number of Machines.

Other Format:

Printed edition:

ISBN:

978-3-540-48413-4

9783540484134

Access Restriction:

Restricted for use by site license.