LEADER 08183nam 22008775 450 001 9910143468603321 005 20250731082112.0 010 $a3-540-49543-6 024 7 $a10.1007/3-540-49543-6 035 $a(CKB)1000000000211017 035 $a(SSID)ssj0000326087 035 $a(PQKBManifestationID)11255374 035 $a(PQKBTitleCode)TC0000326087 035 $a(PQKBWorkID)10265221 035 $a(PQKB)10101487 035 $a(DE-He213)978-3-540-49543-7 035 $a(MiAaPQ)EBC3071987 035 $a(MiAaPQ)EBC6485687 035 $a(PPN)15522770X 035 $a(BIP)47743255 035 $a(EXLCZ)991000000000211017 100 $a20121227d1998 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aRandomization and Approximation Techniques in Computer Science $eSecond International Workshop, RANDOM?98, Barcelona, Spain, October 8?10, 1998 Proceedings /$fedited by Michael Luby, Jose Rolim, Maria Serna 205 $a1st ed. 1998. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1998. 215 $a1 online resource (IX, 385 p.) 225 1 $aLecture Notes in Computer Science,$x1611-3349 ;$v1518 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-65142-X 320 $aIncludes bibliographical references and index. 327 $aInvited 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 DenseInstances of Non-Boolean Optimization Problems -- Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow. 330 $aTheWorkshoponRandomizationandApproximationTechniquesinComputer 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,MichaelMitzenmacher Andr´eaW. Richa,RameshK. 410 0$aLecture Notes in Computer Science,$x1611-3349 ;$v1518 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aArtificial intelligence$xData processing 606 $aMathematical optimization 606 $aCalculus of variations 606 $aMathematical statistics 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aData Science 606 $aCalculus of Variations and Optimization 606 $aDiscrete Mathematics 606 $aProbability and Statistics in Computer Science 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aArtificial intelligence$xData processing. 615 0$aMathematical optimization. 615 0$aCalculus of variations. 615 0$aMathematical statistics. 615 14$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aData Science. 615 24$aCalculus of Variations and Optimization. 615 24$aDiscrete Mathematics. 615 24$aProbability and Statistics in Computer Science. 676 $a004.015114 702 $aLuby$b Michael George 702 $aRolim$b Jose? D. P. 702 $aSerna$b Maria$f1959- 712 12$aInternational Workshop on Randomization and Approximation Techniques in Computer Science 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910143468603321 996 $aRandomization and Approximation Techniques in Computer Science$92072177 997 $aUNINA