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 /

• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Άλλοι συγγραφείς: Hochbaum, Dorit (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt), Jansen, Klaus (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt), Rolim, Jose D.P (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt), Sinclair, Alistair (Επιμελητής έκδοσης, http://id.loc.gov/vocabulary/relators/edt)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1999.
• Έκδοση: 1st ed. 1999.
• Σειρά: Lecture Notes in Computer Science, 1671
• Θέματα: Computer programming.; Probabilities.; Data structures (Computer science).; Algorithms.; Computer science-Mathematics.; Programming Techniques.; Probability Theory and Stochastic Processes.; Data Structures and Information Theory.; Algorithm Analysis and Problem Complexity.; Discrete Mathematics in Computer Science.; Data Structures.

Πίνακας περιεχομένων:

• 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
• Invited Talk
• 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.