Martti Penttonen / Erik Meineche Schmidt (eds.)

Algorithm Theory - SWAT 2002

8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings
Herausgegeben:Penttonen, Martti; Meineche Schmidt, Erik

• Broschiertes Buch

Produktbeschreibung

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 APTASfortheSingleM

Produktdetails

• Lecture Notes in Computer Science 2368
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-540-43866-3
• 2002
• Seitenzahl: 468
• Erscheinungstermin: 19. Juni 2002
• Englisch
• Abmessung: 235mm x 155mm x 26mm
• Gewicht: 653g
• ISBN-13: 9783540438663
• ISBN-10: 3540438661
• Artikelnr.: 23303586

Autorenporträt

Martti Penttonen, University of Kuopio, Finland / Erik Meineche Schmidt, University of Aarhus, Denmark

Inhaltsangabe

Invited Speakers.- An Efficient Quasidictionary.- Combining Pattern Discovery and Probabilistic Modeling in Data Mining.- Scheduling.- Time and Space Efficient Multi-method Dispatching.- Linear Time Approximation Schemes for Vehicle Scheduling.- Minimizing Makespan for the Lazy Bureaucrat Problem.- A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times.- Computational Geometry.- Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains.- Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D.- Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains.- Exact Algorithms and Approximation Schemes for Base Station Placement Problems.- A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels.- Optimal Algorithm for a Special Point-Labeling Problem.- Random Arc Allocation and Applications.- On Neighbors in Geometric Permutations.- Graph Algorithms.- Powers of Geometric Intersection Graphs and Dispersion Algorithms.- Efficient Data Reduction for Dominating Set: A Linear Problem Kernel for the Planar Case.- Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous.- Approximation Hardness of the Steiner Tree Problem on Graphs.- The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus.- The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms.- A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid.- Approximation Algorithms for Edge-Dilation k-Center Problems.- Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm.- Improved Algorithms for the Random Cluster Graph Model.-?-List Vertex Coloring in Linear Time.- Robotics.- Robot Localization without Depth Perception.- Online Parallel Heuristics and Robot Searching under the Competitive Framework.- Analysis of Heuristics for the Freeze-Tag Problem.- Approximation Algorithms.- Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems.- All-Norm Approximation Algorithms.- Approximability of Dense Instances of Nearest Codeword Problem.- Data Communication.- Call Control with k Rejections.- On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem.- Packet Bundling.- Algorithms for the Multi-constrained Routing Problem.- Computational Biology.- Computing the Threshold for q-Gram Filters.- On the Generality of Phylogenies from Incomplete Directed Characters.- Data Storage and Manipulation.- Sorting with a Forklift.- Tree Decompositions with Small Cost.- Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition.- Performance Tuning an Algorithm for Compressing Relational Tables.- A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset.- Paging on a RAM with Limited Resources.- An Optimal Algorithm for Finding NCA on Pure Pointer Machines.- Amortized Complexity of Bulk Updates in AVL-Trees.