Randomization and Approximation Techniques in Computer Science: Second International Workshop, Random'98, Barcelona, Spain, October 8-10, 1998 Proceed

ISBN-13: 9783540651420 / Angielski / Miękka / 1998 / 385 str.

Michael G. Luby; Jose D. P. Rolim; Maria Serna

Opis

TheWorkshoponRandomizationandApproximationTechniquesinComputer Science, Random 98, focuses on algorithmic and complexity aspects arising inthedevelopmentofe cientrandomizedsolutionstocomputationallydi cult problems. Itaims, inparticular, atfosteringthecooperationamongpractitioners andtheoreticiansandamongalgorithmicandcomplexityresearchersinthe eld. RANDOM 98, heldattheUniversityofBarcelona(UPC), October8{10,1998, isthesecondintheseries, afterBologna. This volume contains all contributed papers accepted for presentation at theworkshop, togetherwithinvitedlecturesbyJosepD az(UPCBarcelona), AlanM. Frieze(CarnegieMellonU. ), MichaelLuby(ICSIBerkeley), andEmo Welzl(ETHZuric ] h). Thecontributedpaperswereselectedoutofseveraldozen submissions received in response to the call for papers. All papers published intheworkshopproceedingswereselectedbytheprogramcommitteeonthe basisofrefereereports. Considerablee ortwasdevotedtotheevaluationofthe submissionsbytheprogramcommitteeandanumberofotherreferees. Extensive feedbackwasprovidedtoauthorsasaresult, whichwehopehasprovenhelpful tothem. Wewouldliketothankalloftheauthorswhorespondedtothecallforpapers, ourinvitedspeakers, thereferees, andthemembersoftheprogramcommittee: MichaelLuby, Chair, ICSIBerkeley AndreiBroder, DigitalSystemsResearchCenter BernardChazelle, PrincetonU. AndreaClementi, U. ofRome AnnaKarlin, U. ofWashington RichardKarp, U. ofWashington ClaireKenyon, U. ofParisSud MichaelMitzenmacher, DigitalSystemsResearchCenter RajeevMotwani, StanfordU. PrabhakarRaghavan, IBM MariaSerna, UPCBarcelona AlistairSinclair, U. ofCalifornia, Berkeley MadhuSudan, MIT AviWigderson, HebrewU. PeterWinkler, BellLabs WegratefullyacknowledgesupportfromtheEuropeanAssociationINTAS, theComissionatperaUniversitatsiRecerca{GeneralitatdeCatalunya, and Universitat Polit ecnica de Catalunya. Finally, we would like to thank Helena Martinez, CarmeAlvarez, ConradoMartinez, andJordiPetitiSilvestrefortheir helpinthepreparationofthemeeting. August1998 MichaelLuby, Jos eD. P. Rolim, MariaJ. Serna Contents Invited Paper Disjoint Paths in Expander Graphs via Random Walks: A Short Survey 1 AlanM. Frieze RegularPapers A Derandomization Using Min-Wise Independent Permutations 15 AndreiZ. Broder, MosesCharikarandMichaelMitzenmacher An Algorithmic Embedding of Graphs via Perfect Matchings 25 VojtechR] odl, AndrzejRucin skiandMichelleWagner Deterministic Hypergraph Coloring and Its Applications 35 Chi-JenLu On the De-randomization of Space-Bounded Computations 47 RoyArmoni Talagrand s Inequality and Locality in Distributed Computing 60 DevdattP. Dubhashi On-Line Bin-Stretching 71 YossiAzarandOdedRegev Combinatorial Linear Programming: Geometry Can Help 82 BerndGar ] tner A Note on Bounding the Mixing Time by Linear Programming 97 AbrahamSharell Robotic Exploration, Brownian Motion and Electrical Resistance 116 IsraelA. Wagner, MichaelLindenbaumandAlfredM. Bruckstein Fringe Analysis of Synchronized Parallel Algorithms on 2-3 Trees 131 RicardoBaeza-Yates, JoaquimGabarro andXavierMesseguer On Balls and Bins with Deletions 145 RichardCole, AlanFrieze, BruceM. Maggs, MichaelMitzenmache

Spis treści

Invited Paper.- Disjoint Paths in Expander Graphs via Random Walks: a Short Survey.- Regular Papers.- A Derandomization Using Min-Wise Independent Permutations.- An Algorithmic Embedding of Graphs via Perfect Matchings.- Deterministic Hypergraph Coloring and Its Applications.- On the Derandomization of Space-Bounded Computations.- Talagrand’s Inequality and Locality in Distributed Computing.- On-line Bin-Stretching.- Combinatorial Linear Programming: Geometry Can Help.- A Note on Bounding the Mixing Time by Linear Programming.- Robotic Exploration, Brownian Motion and Electrical Resistance.- Fringe analysis of synchronized parallel algorithms on 2–3 trees.- On Balls and Bins with Deletions.- “Balls into Bins” — A Simple and Tight Analysis.- Invited Paper.- Tornado Codes: Practical Erasure Codes Based on Random Irregular Graphs.- Regular Papers.- Using Approximation Hardness to Achieve Dependable Computation.- Complexity of Sequential Pattern Matching Algorithms.- A Random Server Model for Private Information Retrieval.- Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract).- Randomized Lower Bounds for Online Path Coloring.- Parallel Random Search and Tabu Search for the Minimal Consistent Subset Selection Problem.- On Various Cooling Schedules for Simulated Annealing Applied to the Job Shop Problem.- A High Performance Approximate Algorithm for the Steiner Problem in Graphs.- Invited Paper.- Random Geometric Problems on [0, 1]2.- Regular Papers.- A Role of Constraint in Self-Organization.- Constructive Bounds and Exact Expectations for the Random Assignment Problem.- The “Burnside Process” Converges Slowly.- Quicksort Again Revisited.- Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.- Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow.