Algorithm Engineering and Experimentation

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 Solvingä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. Fino