基本説明
Subseries: Theoretical Computer Science and General Issues.
Full Description
The 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.
Contents
WAOA 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.
