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 : proceedings

Dorit Hochbaum [et al.] (eds.)

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.

「Nielsen BookData」より

[目次]

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

「Nielsen BookData」より

この本の情報

書名 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 : proceedings
著作者等 Hochbaum, Dorit S.
Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Workshop on Randomization and Approximation Techniques in Computer Science
Jansen Klaus
Rolim Jose D.P.
Sinclair Alistair
Hochbaum Dorit
シリーズ名 Lecture notes in computer science
出版元 Springer
刊行年月 c1999
ページ数 ix, 287 p.
大きさ 24 cm
ISBN 3540663290
NCID BA42649120
※クリックでCiNii Booksを表示
言語 英語
出版国 ドイツ
この本を: 
このエントリーをはてなブックマークに追加

このページを印刷

外部サイトで検索

この本と繋がる本を検索

ウィキペディアから連想