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.

This book constitutes the refereed proceedings of the 6th International Frontiers of Algorithmics Workshop, FAW 2012, and the 8th International Conference on Algorithmic Aspects in Information and Management, AAIM 2012, jointly held in Beijing, China, in May 2012. The 33 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 81 submissions. The papers are organized in topical sections on algorithms and data structures, algorithmic game theory and incentive analysis, biomedical imaging algorithms, communication networks and optimization, computational learning theory, knowledge discovery, and data mining, experimental algorithmic methodologies, optimization algorithms in economic and operations research, pattern recognition algorithms and trustworthy algorithms and trustworthy software.

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.

This book constitutes the refereed proceedings of the 6th International Frontiers of Algorithmics Workshop, FAW 2012, and the 8th International Conference on Algorithmic Aspects in Information and Management, AAIM 2012, jointly held in Beijing, China, in May 2012. The 33 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 81 submissions. The papers are organized in topical sections on algorithms and data structures, algorithmic game theory and incentive analysis, biomedical imaging algorithms, communication networks and optimization, computational learning theory, knowledge discovery, and data mining, experimental algorithmic methodologies, optimization algorithms in economic and operations research, pattern recognition algorithms and trustworthy algorithms and trustworthy software.