|
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 IngeLiGørtz UlrichMeyer HolgerBlaar MikaelHammar PeterBroMiltersen JeanBlair IiroHonkala MichaelMinock JormaBoberg HeikkiHyyr¨o PatMorin JesperBojesen ChristianIcking ErkkiM¨akinen GerthS. Brodal TiborJordan RasmusPagh WentongCai DavidGroveJørgensen 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 SørenSkov J. Urrutia TheisRauhe ChristianSloper PawelWinter FrederikRønn RobertoSolis-Oba LarsYde PeterSanders Hans-HenrikStærfeldt 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 Stølting Brodal, Inge Li Gørtz, 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.
|
