LEADER 06153nam 22008895 450 001 9910484165803321 005 20251226203013.0 010 $a1-280-38624-X 010 $a9786613564160 010 $a3-642-12450-X 024 7 $a10.1007/978-3-642-12450-1 035 $a(CKB)2550000000011525 035 $a(SSID)ssj0000399470 035 $a(PQKBManifestationID)11250024 035 $a(PQKBTitleCode)TC0000399470 035 $a(PQKBWorkID)10375777 035 $a(PQKB)10191760 035 $a(DE-He213)978-3-642-12450-1 035 $a(MiAaPQ)EBC3065267 035 $a(OCoLC)ocn646812614 035 $a(DLC) 2010924119 035 $a(PPN)149073348 035 $a(BIP)30141884 035 $a(EXLCZ)992550000000011525 100 $a20100509d2010 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation and Online Algorithms $e7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009 Revised Papers /$fedited by Evripidis Bampis, Klaus Jansen 205 $a1st ed. 2010. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2010. 215 $a1 online resource (X, 255 p. 23 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5893 300 $aInternational conference proceedings. 311 08$a3-642-12449-6 320 $aIncludes bibliographical references and index. 327 $aWAOA 2009 -- On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems -- Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications -- Price Fluctuations: To Buy or to Rent -- Approximation Algorithms for Multiple Strip Packing -- Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window -- Longest Wait First for Broadcast Scheduling [Extended Abstract] -- The Routing Open Shop Problem: New Approximation Algorithms -- On the Price of Stability for Undirected Network Design -- Finding Dense Subgraphs in G(n,1/2) -- Parameterized Analysis of Paging and List Update Algorithms -- Online Scheduling of Bounded Length Jobs to Maximize Throughput -- On the Additive Constant of the k-Server Work Function Algorithm -- A (4?+??)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs -- Guard Games on Graphs: Keep the Intruder Out! -- Between a Rock and a Hard Place: The Two-to-One Assignment Problem -- Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width -- Online Minimization Knapsack Problem -- Optimization Problems in Multiple Subtree Graphs -- Multi-Criteria TSP: Min and Max Combined -- Packet Routing: Complexity and Algorithms -- Minimal Cost Reconfiguration of Data Placement in Storage Area Network -- Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing. 330 $aThe 7th Workshop on Approximation and Online Algorithms (WAOA 2009) focused on the design and analysis of algorithms for online and computati- ally hard problems. Both kinds of problems have a large number of applications from a variety of ?elds. WAOA 2009 took place in Copenhagen, Denmark, d- ing September 10-11, 2009. The workshop was part of the ALGO 2009 event that also hosted ESA 2009, IWPEC 2009, and ATMOS 2009. The previous WAOA workshops were held in Budapest (2003), Rome (2004), Palma de M- lorca(2005),Zurich(2006),Eilat(2007),andKarlsruhe(2008).The proceedings ofthesepreviousWAOAworkshopshaveappearedasLNCSvolumes2909,3351, 3879, 4368, 4927, and 5426, respectively. Topics of interest for WAOA 2009 were: algorithmic game theory, appr- imation classes, coloring and partitioning, competitive analysis, computational ?nance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximationand online algorithms,parameterizedcomplexity, randomization techniques, real-world applications, and scheduling problems. In response to the call for papers, we received 62 submissions. Each subm- sionwasreviewedbyatleastthreereferees,andthevastmajoritybyatleastfour referees. The submissions were mainly judged on originality, technical quality, andrelevanceto the topics of the conference.Basedon the reviews,the Program Committee selected 22 papers. We are grateful to Andrei Voronkov for providing the EasyChair conference system,whichwasusedtomanagetheelectronicsubmissions,thereviewprocess, and the electronic PC meeting. It made our task much easier. We would also like to thank all the authors who submitted papers to WAOA 2009 as well as the local organizers of ALGO 2009. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5893 606 $aComputer programming 606 $aComputer science 606 $aApplication software 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aProgramming Techniques 606 $aTheory of Computation 606 $aComputer and Information Systems Applications 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 615 0$aComputer programming. 615 0$aComputer science. 615 0$aApplication software. 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 14$aProgramming Techniques. 615 24$aTheory of Computation. 615 24$aComputer and Information Systems Applications. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 676 $a005.11 701 $aBampis$b Evripidis$01754801 701 $aJansen$b Klaus$0867301 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484165803321 996 $aApproximation and online algorithms$94192665 997 $aUNINA