Algorithm Engineering and Experiments
4th International Workshop, ALENEX 2002, San Francicsco, CA, USA, January 4-5, 2002, Revised Papers
Published on 24. July 2002
Book
Paperback/Softback
VIII, 212 pages
978-3-540-43977-6 (ISBN)
Description
TheannualworkshoponAlgorithmEngineeringandExperiments(ALENEX) providesaforumforthepresentationoforiginalresearchintheimplementation andexperimentalevaluationofalgorithmsanddatastructures. ALENEX2002 wasthefourthworkshopinthisseries. ItwasheldinSanFrancisco,California onJanuary4-5,2002. Thisvolumecollectsextendedversionsofthe15papers thatwereselectedforpresentationfromapoolof34submissions. Wewouldliketothankthesponsors,authors,andreviewerswhohelpedmake ALENEX2002asuccess. Wealsowanttothanktheinvitedspeakers,Cynthia PhillipsofSandiaNationalLaboratories,MartinFarach-ColtonofGoogle,and MichaelKassofPixar. Finally,wewouldliketothankSpringer-Verlagfor- blishingthesepapersintheirLectureNotesinComputerScience series. May2002 DavidM. Mount Cli?ordStein ALENEX2002Sponsors Thefollowingorganizationsprovideddirect?nancialsupport,whichenabledus tohostinvitedspeakersandprovidereducedregistrationfeesforstudents. *SandiaNationalLaboratories *AkamiTechnologiesInc. *NECResearch Thefollowingprovidedin-kindsupport,facilitatingtheworkshop.
*SIAM,theSocietyforIndustrialandAppliedMathematics *SIGACT,theACMSIGonAlgorithmsandComputationTheory *ColumbiaUniversity ALENEX2002ProgramCommittee NancyAmato(TexasA&MUniversity) MarshallBern(XeroxPARC) MichaelGoodrich(UniversityofCalifornia,Irvine) TomMcCormick(UniversityofBritishColumbia) MichaelMitzenmacher(HarvardUniversity) DavidMount(UniversityofMaryland;Co-chair) GiriNarasimhan(FloridaInternationalUniversity) RajeevRaman(UniversityofLeicester) Cli?ordStein(ColumbiaUniversity;Co-chair) VI ALENEX2002 ALENEX2002SteeringCommittee MichaelGoodrich(UniversityofCalifornia,Irvine) AdamBuchsbaum(AT&TLabs) RobertoBattiti(UniversityofTrento,Italy) AndrewV. Goldberg(IntertrustSTARLab) MichaelT. Goodrich(UniversityofCalifornia,Irvine) DavidS. Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E. Moret(UniversityofNewMexico;chair) JackSnoeyink(UNC-ChapelHill) TableofContents ALENEX2002 OntheImplementationofMST-BasedHeuristicsfortheSteinerProblem inGraphs...1 M. PoggideArag"ao,R. F. Werneck(CatholicUniversityof RiodeJaneiro) ATime-SensitiveSystemforBlack-BoxCombinatorialOptimization ...16 V. Phan,P. Sumazin,S.
Skiena(SUNYStonyBrook) ACompressedBreadth-FirstSearchforSatis?ability ...29 D. B. Motter,I. L. Markov(UniversityofMichigan) UsingMulti-levelGraphsforTimetableInformationinRailwaySystems . . 43 F. Schulz,D. Wagner(UniversityofKonstanz),C. Zaroliagis (UniversityofPatras) EvaluatingtheLocalRatioAlgorithmforDynamicStorageAllocation ...60 K. Pruhs(UniversityofPittsburgh),E. Wiewiora(Universityof California,SanDiego) An Experimental Study of Prefetching and Caching Algorithms for the WorldWideWeb ...71 M. Curcio,S. Leonardi,A. Vitaletti (Universit'adiRoma"LaSapienza") TheTreewidthofJavaPrograms...86 J. Gustedt(LORIA&INRIALorraine),O. A. Maehle,J. A. Telle (UniversityofBergen) PartitioningPlanarGraphswithCostsandWeights...98 L. Aleksandrov(BulgarianAcademyofSciences,CarletonUniversity), H. Djidjev(UniversityofWarwick),H. Guo,A. Maheshwari (CarletonUniversity) MaintainingDynamicMinimumSpanningTrees:AnExperimentalStudy . 111 G. Cattaneo,P. Faruolo,U. F. Petrillo(Universit'adiSalerno), G. F. Italiano(Universit'adiRoma"TorVergata") ExperimentalEvaluationofaNewShortestPathAlgorithm ...126 S. Pettie,V. Ramachandran,S. Sridhar(UniversityofTexasatAustin) GettingMorefromOut-of-CoreColumnsort...1
43 G. Chaudhry,T. H. Cormen(DartmouthCollege) VIII TableofContents TopologicalSweepinDegenerateCases ...155 E. Rafalin,D. Souvaine(TuftsUniversity),I. Streinu(SmithCollege) AccelerationofK-MeansandRelatedClusteringAlgorithms...166 S. J. Phillips(AT&TLabs-Research) STAR-Tree:AnE?cientSelf-AdjustingIndexforMovingObjects ...178 C. M. Procopiuc(AT&TResearchLab),P. K. Agarwal (DukeUniversity),S. Har-Peled(UniversityofIllinois) AnImprovementonTreeSelectionSort...194 J. Chen(BellLabsResearch,Beijing) AuthorIndex...207 OntheImplementationofMST-Based HeuristicsfortheSteinerProbleminGraphs Marcus Poggi de Arag" ao and Renato F. Werneck DepartmentofInformatics,CatholicUniversityofRiodeJaneiro,R. MarquesdeS"ao Vicente,225,RiodeJaneiro,RJ,22453-900,Brazil. poggi@inf. puc-rio. br,rwerneck@cs. princeton. edu Abstract. Someofthemostwidelyusedconstructiveheuristicsforthe Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine e?cient implem- tations of heuristics based on the classic algorithms by Prim, Kruskal, and Bor? uvka.
*SIAM,theSocietyforIndustrialandAppliedMathematics *SIGACT,theACMSIGonAlgorithmsandComputationTheory *ColumbiaUniversity ALENEX2002ProgramCommittee NancyAmato(TexasA&MUniversity) MarshallBern(XeroxPARC) MichaelGoodrich(UniversityofCalifornia,Irvine) TomMcCormick(UniversityofBritishColumbia) MichaelMitzenmacher(HarvardUniversity) DavidMount(UniversityofMaryland;Co-chair) GiriNarasimhan(FloridaInternationalUniversity) RajeevRaman(UniversityofLeicester) Cli?ordStein(ColumbiaUniversity;Co-chair) VI ALENEX2002 ALENEX2002SteeringCommittee MichaelGoodrich(UniversityofCalifornia,Irvine) AdamBuchsbaum(AT&TLabs) RobertoBattiti(UniversityofTrento,Italy) AndrewV. Goldberg(IntertrustSTARLab) MichaelT. Goodrich(UniversityofCalifornia,Irvine) DavidS. Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E. Moret(UniversityofNewMexico;chair) JackSnoeyink(UNC-ChapelHill) TableofContents ALENEX2002 OntheImplementationofMST-BasedHeuristicsfortheSteinerProblem inGraphs...1 M. PoggideArag"ao,R. F. Werneck(CatholicUniversityof RiodeJaneiro) ATime-SensitiveSystemforBlack-BoxCombinatorialOptimization ...16 V. Phan,P. Sumazin,S.
Skiena(SUNYStonyBrook) ACompressedBreadth-FirstSearchforSatis?ability ...29 D. B. Motter,I. L. Markov(UniversityofMichigan) UsingMulti-levelGraphsforTimetableInformationinRailwaySystems . . 43 F. Schulz,D. Wagner(UniversityofKonstanz),C. Zaroliagis (UniversityofPatras) EvaluatingtheLocalRatioAlgorithmforDynamicStorageAllocation ...60 K. Pruhs(UniversityofPittsburgh),E. Wiewiora(Universityof California,SanDiego) An Experimental Study of Prefetching and Caching Algorithms for the WorldWideWeb ...71 M. Curcio,S. Leonardi,A. Vitaletti (Universit'adiRoma"LaSapienza") TheTreewidthofJavaPrograms...86 J. Gustedt(LORIA&INRIALorraine),O. A. Maehle,J. A. Telle (UniversityofBergen) PartitioningPlanarGraphswithCostsandWeights...98 L. Aleksandrov(BulgarianAcademyofSciences,CarletonUniversity), H. Djidjev(UniversityofWarwick),H. Guo,A. Maheshwari (CarletonUniversity) MaintainingDynamicMinimumSpanningTrees:AnExperimentalStudy . 111 G. Cattaneo,P. Faruolo,U. F. Petrillo(Universit'adiSalerno), G. F. Italiano(Universit'adiRoma"TorVergata") ExperimentalEvaluationofaNewShortestPathAlgorithm ...126 S. Pettie,V. Ramachandran,S. Sridhar(UniversityofTexasatAustin) GettingMorefromOut-of-CoreColumnsort...1
43 G. Chaudhry,T. H. Cormen(DartmouthCollege) VIII TableofContents TopologicalSweepinDegenerateCases ...155 E. Rafalin,D. Souvaine(TuftsUniversity),I. Streinu(SmithCollege) AccelerationofK-MeansandRelatedClusteringAlgorithms...166 S. J. Phillips(AT&TLabs-Research) STAR-Tree:AnE?cientSelf-AdjustingIndexforMovingObjects ...178 C. M. Procopiuc(AT&TResearchLab),P. K. Agarwal (DukeUniversity),S. Har-Peled(UniversityofIllinois) AnImprovementonTreeSelectionSort...194 J. Chen(BellLabsResearch,Beijing) AuthorIndex...207 OntheImplementationofMST-Based HeuristicsfortheSteinerProbleminGraphs Marcus Poggi de Arag" ao and Renato F. Werneck DepartmentofInformatics,CatholicUniversityofRiodeJaneiro,R. MarquesdeS"ao Vicente,225,RiodeJaneiro,RJ,22453-900,Brazil. poggi@inf. puc-rio. br,rwerneck@cs. princeton. edu Abstract. Someofthemostwidelyusedconstructiveheuristicsforthe Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine e?cient implem- tations of heuristics based on the classic algorithms by Prim, Kruskal, and Bor? uvka.
More details
Series
Edition
2002 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
VIII, 212 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 13 mm
Weight
341 gr
ISBN-13
978-3-540-43977-6 (9783540439776)
DOI
10.1007/3-540-45643-0
Schweitzer Classification
Other editions
Additional editions
David M. Mount | Clifford Stein
Algorithm Engineering and Experiments
4th International Workshop, ALENEX 2002, San Francicsco, CA, USA, January 4-5, 2002, Revised Papers
E-Book
01/2002
Springer
€53.49
Available for download
Content
ALENEX 2002.- On the Implementation of MST-Based Heuristics for the Steiner Problem in Graphs.- A Time-Sensitive System for Black-Box Combinatorial Optimization.- A Compressed Breadth-First Search for Satisfiability.- Using Multi-level Graphs for Timetable Information in Railway Systems.- Evaluating the Local Ratio Algorithm for Dynamic Storage Allocation.- An Experimental Study of Prefetching and Caching Algorithms for the World Wide Web.- The Treewidth of Java Programs.- Partitioning Planar Graphs with Costs and Weights.- Maintaining Dynamic Minimum Spanning Trees: An Experimental Study.- Experimental Evaluation of a New Shortest Path Algorithm.- Getting More from Out-of-Core Columnsort.- Topological Sweep in Degenerate Cases.- Acceleration of K-Means and Related Clustering Algorithms.- STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects.- An Improvement on Tree Selection Sort.