Algorithm Engineering and Experiments 4th International Workshop, ALENEX 2002, San Francicsco, CA, USA, January 4-5, 2002, Revised Papers
Heftet /
2002
/ Engelsk
Produktdetaljer
ISBN
9783540439776
Publisert
2002-07-24
Utgiver
Vendor
Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Høyde
235 mm
Bredde
155 mm
Aldersnivå
Research, UU, UP, P, 05, 06
Språk
Product language
Engelsk
Format
Product format
Heftet
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.
Les mer
Constituting the post-proceedings of the 4th International Workshop on Algorithm Engineering and Experiments, these papers address such topics as: heuristics for algorithms; combinatorial optimization; searching; graph computation; network optimization; scheduling and computational geometry.
Les mer
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.
Les mer
Springer Book Archives
Springer Book Archives
Includes supplementary material: sn.pub/extras
Produktdetaljer
ISBN
9783540439776
Publisert
2002-07-24
Utgiver
Vendor
Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Høyde
235 mm
Bredde
155 mm
Aldersnivå
Research, UU, UP, P, 05, 06
Språk
Product language
Engelsk
Format
Product format
Heftet