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.
Reihe
Auflage
Sprache
Verlagsort
Verlagsgruppe
Zielgruppe
Für höhere Schule und Studium
Für Beruf und Forschung
Research
Illustrationen
Maße
Höhe: 235 mm
Breite: 155 mm
Dicke: 14 mm
Gewicht
ISBN-13
978-3-540-42560-1 (9783540425601)
DOI
Schweitzer Klassifikation
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.
