Erik Meineche Schmidt – författare

Experimental algorithmics, as its name indicates, combines algorithmic work and experimentation: algorithms are not just designed, but also implemented and tested on a variety of instances. Perhaps the most important lesson in this process is that designing an algorithm is but the first step in the process of developing robust and efficient software for applications.Based on a seminar held at Dagstuhl Castle, Germany in September 2000, this state-of-the-art survey presents a coherent survey of the work done in the area so far. The 11 carefully reviewed chapters provide complete coverage of all current topics in experimental algorithmics.

ThepapersinthisvolumewerepresentedatSWAT2002,theEighthScandi- vianWorkshoponAlgorithmTheory. Theworkshop,whichisreallyaconference, hasbeenheldbienniallysince1988,rotatingbetweenthe?veNordiccountries (Denmark,Finland,Iceland,Norway,andSweden). Italsohasalooseassoc- tionwiththeWADS(WorkshoponAlgorithmsandDataStructures)conference thatisheldinoddnumberedyears. SWATisintendedasaforumforrese- chersintheareaofdesignandanalysisofalgorithms. TheSWATconferences arecoordinatedbytheSWATsteeringcommittee,whichconsistsofB. Aspvall (Bergen),S. Carlsson(Lule? a),H. Hafsteinsson(Iceland),R. Karlsson(Lund), ? A. Lingas(Lund),E. M. Schmidt(Arhus),andE. Ukkonen(Helsinki). Thecallforpaperssoughtcontributionsinallareasofalgorithmsanddata structures,includingcomputationalgeometry,parallelanddistributedcom- ting, graph theory, computational biology, and combinatorics. A total of 103 papers were submitted, out of which the program committee selected 43 for presentation. In addition, invited lectures were presented by Torben Hagerup (Frankfurt)andHeikkiMannila(Helsinki). SWAT2002washeldinTurku,July3-5,2002,andwaslocallyorganizedbya committeeconsistingofT. J..arvi(chair),L. Bergroth,T. Kaukoranta,T.Raita, J. Smed,andJ. Teuhola(secr. ),allfromtheDepartmentofComputerScience, UniversityofTurku. Wewishtothankalltherefereeswhoaidedinevaluatingthepapers. Wealso thanktheAcademyofFinland,TurkuCentreforComputerScience(TUCS), andTurkuUniversityFoundationfor?nancialsupport. July2002 MarttiPenttonen ErikMeinecheSchmidt Organization SWAT2002wasorganizedbytheDepartmentofComputerScience,University ofTurku. ProgramCommittee MarttiPenttonen,UniversityofKuopio(co-chair) ? ErikMeinecheSchmidt,Universityof Arhus(co-chair) MicahAdler,UniversityofMassachusetts MartinDietzfelbinger,TechnischeUniversit..atIlmenau PinarHeggernes,UniversityofBergen GiuseppeF. Italiano,UniversityofRome HaimKaplan,TelAvivUniversity RolfKarlsson,UniversityofLund JyrkiKatajainen,UniversityofCopenhagen OlliNevalainen,UniversityofTurku JopSibeyn,UniversityofUme? a MichielSmid,CarletonUniversity Referees IstoAho RolfFagerberg ChristosLevcopoulos TeroAittokallio JiriFiala MosheLewenstein LyudmilAleksandrov JarlFriis AndrzejLingas StephenAlstrup LeszekG,asieniec Eva-MartaLundell MattiasAndersson JordanGergov BengtNilsson EstieArkin HectorGonzalez-Banos JyrkiNummenmaa LasseBergroth HenrikGrove JeppeNejsumMadsen AnneBerry JoachimGudmundsson FredrikManne PhilipBille IngeLiGortz UlrichMeyer HolgerBlaar MikaelHammar PeterBroMiltersen JeanBlair IiroHonkala MichaelMinock JormaBoberg HeikkiHyyr..o PatMorin JesperBojesen ChristianIcking ErkkiM..akinen GerthS. Brodal TiborJordan RasmusPagh WentongCai DavidGroveJorgensen TomiPasanen JianerChen JarkkoKari ChristianN. S. Pedersen ArturCzumaj MichaelKaufmann MortenNicolajPedersen CamilDemetrescu TimoKnuutila MiaPersson AndersDessmark PetterKristiansen ElyPorat FrankDrewes ElmarLangetepe AndrzejProskurowski X Organization YuvalRabani MikkelSigurd JanArneTelle PrabhakarRagde SteveSkiena JukkaTeuhola JagathRajapakse SorenSkov J. Urrutia TheisRauhe ChristianSloper PawelWinter FrederikRonn RobertoSolis-Oba LarsYde PeterSanders Hans-HenrikStaerfeldt MartinZachariasen PetraSche?er KokichiSugihara RodedSharan ArieTamir TableofContents InvitedSpeakers AnE?cientQuasidictionary...1 Torben Hagerup, Rajeev Raman CombiningPatternDiscoveryandProbabilisticModelinginData Mining...19 Heikki Mannila Scheduling TimeandSpaceE?cientMulti-methodDispatching ...20 Stephen Alstrup, Gerth Stolting Brodal, Inge Li Gortz, Theis Rauhe LinearTimeApproximationSchemesforVehicleScheduling...30 John E. Augustine, Steven S. Seiden MinimizingMakespanfortheLazyBureaucratProblem...40 Clint Hepner, Cli?Stein APTASfortheSingleMachineSchedulingProblemwith ControllableProcessingTimes...51 Monaldo Mastrolilli ComputationalGeometry OptimumInapproximabilityResultsforFindingMinimumHidden GuardSetsinPolygonsandTerrains...60 Stephan Eidenbenz SimplexRangeSearchingandkNearestNeighborsofaLine Segmentin2D ...69 Partha P. Goswami, Sandip Das, Subhas C.