Algorithm Engineering and Experimentation
Third International Workshop, ALENEX 2001, Washington, DC, USA, January 5-6, 2001. Revised Papers
Published on 12. September 2001
Book
Paperback/Softback
VIII, 236 pages
978-3-540-42560-1 (ISBN)
Description
The aim of the annual Workshop on Algorithm Engineering and Experiments (ALENEX)istoprovideaforumforthepresentationoforiginalresearchinthe implementationandexperimentalevaluationofalgorithmsanddatastructures. ALENEX2001,thethirdintheseries,washeldinWashington,DC,onJanuary 5-6, 2001. This volume collects extended versions of the 15 papers that were selected for presentation from a pool of 31 submissions. It also includes the abstracts from the three invited speakers, who were supported by DIMACS SpecialFocusonNextGenerationNetworks. Wewouldliketotakethisopportunitytothankthesponsors,authors,and reviewers that made ALENEX 2001 a success. We would also like to thank Springer-Verlag for publishing these papers in their series ofLecture Notes in ComputerScience. June2001 AdamBuchsbaum JackSnoeyink ALENEX2001Sponsors Thefollowingprovideddirect?nancialsupport,whichenabledustohostinvited speakersandprovidereducedregistrationfeestostudents. *DIMACSSpecialFocusonNextGenerationNetworks *TheHopkinsCenterforAlgorithmEngineering *NECResearchInstitute Thefollowingprovidedin-kindsupport,facilitatingtheworkshop.
*AT&T *SIAM,theSocietyforIndustrialandAppliedMathematics *SIGACT,theACMSIGonAlgorithmsandComputationTheory ALENEX2001ProgramCommittee NinaAmenta,(UniversityofTexas,Austin) AdamBuchsbaum,(AT&TLabs-Research;Co-chair) RudolfFleischer,(HongKongUniversityofScience&Technology) LyleMcGeoch,(AmherstCollege) S. Muthukrishnan,(AT&TLabs-Research) JackSnoeyink,(UniversityofNorthCarolina,ChapelHill;Co-chair) MattStallmann(NorthCarolinaStateUniversity) DorotheaWagner(Universit. atKonstanz) VI Preface ALENEX'01ExternalReviewers SunilArya RolfDrechsler MarinaPapatrianta?lou LydiaAyers LeszekGasieniec FrankSchulz ThereseBiedl Ra?aeleGiancarlo MichaelSeel UlrikBrandes RobertoGrossi JopSibeyn FrancBrglez DavidJohnson RobertoSolis-Oba KenClarkson JuhaK.. arkk. ainen ThomasWillhalm SabineCornelsen BernardMoret ALENEXSteeringCommittee RobertoBattiti(UniversityofTrento,Italy) AndrewV. Goldberg(IntertrustSTARLab) MichaelT. Goodrich(JohnsHopkinsUniversity) DavidS. Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E.
Moret(UniversityofNewMexico,chair) TableofContents ALENEX'01 Solvinga"Hard"ProblemtoApproximatean"Easy"One:Heuristicsfor MaximumMatchingsandMaximumTravelingSalesmanProblems...1 S. P. Fekete (TU Berlin), H. Meijer (Queen's University), A. Rohe (Universit. atBonn),andW. Tietze(TUBerlin) CNOP-APackageforConstrainedNetworkOptimization...17 K. MehlhornandM. Ziegelmann(MPISaarbrucken) .. TheAsymmetricTravelingSalesmanProblem: Algorithms,InstanceGenerators,andTests...32 J. Cirasella (Boston Arch. Center Library), D. S. Johnson (AT&T), L. A. McGeoch,(AmherstCollege),andW. Zhang(WUSTL) NetworkTomographythroughEnd-to-EndMeasurements ...60 D. Towsley(UMass. ,Amherst) ExperimentalResultsonStatisticalApproaches toPageReplacementPolicies...61 V. Leung (Sandia National Laboratories) and S. Irani (University of California,Irvine) EstimatingResemblanceofMIDIDocuments...78 M. MitzenmacherandS. Owen(Harvard) ExperimentsonAdaptiveSetIntersectionsforTextRetrievalSystems...91 E. D. Demaine(UWaterloo),A. L' opez-Ortiz(Univ. ofNewBrunswick), andJ. I. Munro(UWaterloo) PVD:AStableImplementationforComputingVoronoiDiagrams ofPolygonalPockets ...105 S. Sethia,M. Held,andJ. S. B.
Mitchell(SUNYStonyBrook) HierarchicalClusteringofTrees:AlgorithmsandExperiments...117 I. FinocchiandR. Petreschi(Universit'adiRoma"LaSapienza") TravelPlanningwithSelf-MadeMaps...132 U. Brandes, F. Schulz, D. Wagner, and T.
*AT&T *SIAM,theSocietyforIndustrialandAppliedMathematics *SIGACT,theACMSIGonAlgorithmsandComputationTheory ALENEX2001ProgramCommittee NinaAmenta,(UniversityofTexas,Austin) AdamBuchsbaum,(AT&TLabs-Research;Co-chair) RudolfFleischer,(HongKongUniversityofScience&Technology) LyleMcGeoch,(AmherstCollege) S. Muthukrishnan,(AT&TLabs-Research) JackSnoeyink,(UniversityofNorthCarolina,ChapelHill;Co-chair) MattStallmann(NorthCarolinaStateUniversity) DorotheaWagner(Universit. atKonstanz) VI Preface ALENEX'01ExternalReviewers SunilArya RolfDrechsler MarinaPapatrianta?lou LydiaAyers LeszekGasieniec FrankSchulz ThereseBiedl Ra?aeleGiancarlo MichaelSeel UlrikBrandes RobertoGrossi JopSibeyn FrancBrglez DavidJohnson RobertoSolis-Oba KenClarkson JuhaK.. arkk. ainen ThomasWillhalm SabineCornelsen BernardMoret ALENEXSteeringCommittee RobertoBattiti(UniversityofTrento,Italy) AndrewV. Goldberg(IntertrustSTARLab) MichaelT. Goodrich(JohnsHopkinsUniversity) DavidS. Johnson(AT&TBellLaboratories) CatherineC. McGeoch(AmherstCollege) BernardM. E.
Moret(UniversityofNewMexico,chair) TableofContents ALENEX'01 Solvinga"Hard"ProblemtoApproximatean"Easy"One:Heuristicsfor MaximumMatchingsandMaximumTravelingSalesmanProblems...1 S. P. Fekete (TU Berlin), H. Meijer (Queen's University), A. Rohe (Universit. atBonn),andW. Tietze(TUBerlin) CNOP-APackageforConstrainedNetworkOptimization...17 K. MehlhornandM. Ziegelmann(MPISaarbrucken) .. TheAsymmetricTravelingSalesmanProblem: Algorithms,InstanceGenerators,andTests...32 J. Cirasella (Boston Arch. Center Library), D. S. Johnson (AT&T), L. A. McGeoch,(AmherstCollege),andW. Zhang(WUSTL) NetworkTomographythroughEnd-to-EndMeasurements ...60 D. Towsley(UMass. ,Amherst) ExperimentalResultsonStatisticalApproaches toPageReplacementPolicies...61 V. Leung (Sandia National Laboratories) and S. Irani (University of California,Irvine) EstimatingResemblanceofMIDIDocuments...78 M. MitzenmacherandS. Owen(Harvard) ExperimentsonAdaptiveSetIntersectionsforTextRetrievalSystems...91 E. D. Demaine(UWaterloo),A. L' opez-Ortiz(Univ. ofNewBrunswick), andJ. I. Munro(UWaterloo) PVD:AStableImplementationforComputingVoronoiDiagrams ofPolygonalPockets ...105 S. Sethia,M. Held,andJ. S. B.
Mitchell(SUNYStonyBrook) HierarchicalClusteringofTrees:AlgorithmsandExperiments...117 I. FinocchiandR. Petreschi(Universit'adiRoma"LaSapienza") TravelPlanningwithSelf-MadeMaps...132 U. Brandes, F. Schulz, D. Wagner, and T.
More details
Series
Edition
2001 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
VIII, 236 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 14 mm
Weight
376 gr
ISBN-13
978-3-540-42560-1 (9783540425601)
DOI
10.1007/3-540-44808-X
Schweitzer Classification
Other editions
Additional editions
Adam L. Buchsbaum | Jack Snoeyink
Algorithm Engineering and Experimentation
Third International Workshop, ALENEX 2001, Washington, DC, USA, January 5-6, 2001. Revised Papers
E-Book
06/2003
Springer
€53.49
Available for download
Content
ALENEX'01.- Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems.- CNOP - A Package for Constrained Network Optimization.- The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests.- Network Tomography through End-to-End Measurements.- Experimental Results on Statistical Approaches to Page Replacement Policies.- Estimating Resemblance of MIDI Documents.- Experiments on Adaptive Set Intersections for Text Retrieval Systems.- PVD: A Stable Implementation for Computing Voronoi Diagrams of Polygonal Pockets.- Hierarchical Clustering of Trees: Algorithms and Experiments.- Travel Planning with Self-Made Maps.- New Algorithmic Challenges Arising in Measurement-Driven Networking Research.- A Probabilistic Spell for the Curse of Dimensionality.- Experimental Evaluation of the Height of a Random Set of Points in a d-Dimensional Cube.- An Empirical Study of a New Approach to Nearest Neighbor Searching.- Spectral Analysis for Data Mining.- Trade Off Between Compression and Search Times in Compact Suffix Array.- Implementation of a PTAS for Scheduling with Release Dates.- Biased Skip Lists for Highly Skewed Access Patterns.