Algorithm Theory - SWAT 2002: 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings: 2368 - Brossura

Schmidt, Erik Meineche; Penttonen, Martti

Brossura

ISBN 10: 3540438661 ISBN 13: 9783540438663

Casa editrice: Springer, 2008

Riassunto

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.

Su questo libro

Contenuti

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.

Dettagli dell'edizione

• Editore: Springer
• Data di pubblicazione: 2008
• Lingua: Inglese
• ISBN 10: 3540438661
• ISBN 13: 9783540438663
• Rilegatura: Copertina flessibile
• Numero di pagine: 468
• Contatto del produttore: Springer Nature Customer Service Center GmbH; ProductSafety@springernature.com; ; Europaplatz 3; Heidelberg; 69115; Germania