LEADER 05249nam 22007335 450 001 996465950503316 005 20230222182325.0 024 7 $a10.1007/b106130 035 $a(CKB)1000000000212842 035 $a(SSID)ssj0000316307 035 $a(PQKBManifestationID)11246732 035 $a(PQKBTitleCode)TC0000316307 035 $a(PQKBWorkID)10263648 035 $a(PQKB)10219755 035 $a(DE-He213)978-3-540-31833-0 035 $a(MiAaPQ)EBC3067984 035 $a(PPN)123092043 035 $a(EXLCZ)991000000000212842 100 $a20100702d2005 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation and Online Algorithms$b[electronic resource] $eSecond International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004, Revised Selected Papers /$fedited by Giuseppe Persiano, Roberto Solis-Oba 205 $a1st ed. 2005. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2005. 215 $a1 online resource (VIII, 295 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v3351 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$aPrinted edition: 9783540245742 320 $aIncludes bibliographical references and index. 327 $aInvited Talks -- Online Packet Switching -- Approximation Algorithms for Mixed Fractional Packing and Covering Problems -- Regular Papers -- Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-Trees -- Online Bin Packing with Resource Augmentation -- A PTAS for Delay Minimization in Establishing Wireless Conference Calls -- This Side Up! -- Approximation Algorithm for Directed Multicuts -- Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria -- Approximation Algorithms for Spreading Points -- More Powerful and Simpler Cost-Sharing Methods -- Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints -- Priority Algorithms for Graph Optimization Problems -- Pricing Network Edges to Cross a River -- Submodular Integer Cover and Its Application to Production Planning -- Stochastic Online Scheduling on Parallel Machines -- A -Approximation Algorithm for Biconnecting a Graph with a Given Hamiltonian Path -- Order-Preserving Transformations and Greedy-Like Algorithms -- Off-line Admission Control for Advance Reservations in Star Networks -- Joint Base Station Scheduling -- Universal Bufferless Routing -- Strong Colorings of Hypergraphs -- Deterministic Monotone Algorithms for Scheduling on Related Machines -- Better Bounds for Minimizing SONET ADMs. 330 $aThe 2nd Workshop on Approximation and Online Algorithms (WAOA 2004) focused on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications arising from a variety of ?elds. WAOA 2004 took place in Bergen, Norway, from September 14 to September 16, 2004. The workshop was part of the ALGO 2004 event which also hosted ESA, WABI, IWPEC, and ATMOS. TopicsofinterestsforWAOA2004were:applicationstogametheory,appr- imation classes, coloring and partitioning, competitive analysis, computational ?nance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, routing, packing and covering, paradigms, randomization techniques, and scheduling problems. In response to our call we received 47 submissions. Each submission was reviewed by at least 3 referees, who judged the paper on originality, quality, and consistency with the topics of the conference. Based on the reviews, the Program Committee selected 21 papers. This volume contains the 21 selected papers and the two invited talks given by Yossi Azar and Klaus Jansen. We thank all the authors who submitted papers to the workshop and we also kindly thank the local organizers of ALGO 2004. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v3351 606 $aAlgorithms 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aComputer graphics 606 $aArtificial intelligence?Data processing 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 606 $aComputer Graphics 606 $aData Science 615 0$aAlgorithms. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 0$aComputer graphics. 615 0$aArtificial intelligence?Data processing. 615 14$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 615 24$aComputer Graphics. 615 24$aData Science. 676 $a005.1 702 $aPersiano$b Giuseppe$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aSolis-Oba$b Roberto$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465950503316 996 $aApproximation and Online Algorithms$92954916 997 $aUNISA