Annotation This book constitutes the thoroughly refereed post workshop proceedings of the 6th International Workshop on Approximation and Online Algorithms, WAOA 2008, held in Karlsruhe, Germany, in September 2008 as part of the ALGO 2008 conference event. The 22 revised full papers presented were carefully reviewed and selected from 56 submissions. The workshop covered areas such as algorithmic game theory, approximation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, randomization techniques, real-world applications, and scheduling problems Cover Front matter 1. Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees Introduction Formulation Improved Approximation Minimum Capacity $\mu$=2 Arbitrary Minimum Capacity Proof of Lemma 4 Hardness of MCFT with Constant Lower Bounds Exact Solution for Spiders Polyhedral Results Closing Remarks 2. Size Versus Stability in the Marriage Problem Size Versus Stability in the Marriage Problem Introduction Unbounded Length Preference Lists Preference Lists of Length at Most 3 Preference Lists on One Side of Length at Most 2 Concluding Remarks 3. Degree-Constrained Subgraph Problems: Hardness and Approximation Results Degree-Constrained Subgraph Problems: Hardness and Approximation Results Introduction Hardness of Approximating MDBCS$_d$ Approximating MDBCS$_d$ Hardness of Approximating MSMD$_d$ Approximating MSMD$_d$ MSMD$_d$ Is in P for Graphs with Small Treewidth Approximation Algorithm for $M$-Minor-Free Graphs Conclusions 4. A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines Introduction The Idea of the Proof The Lower Bound Conclusions 5. Improved Randomized Online Scheduling of Unit Length Intervals and Jobs Improved Randomized Online Scheduling of Unit Length Intervals and Jobs Introduction Preliminaries A 2-Competitive Barely Random Algorithm for Intervals A 3-Competitive Barely Random Algorithm for Jobs Lower Bound A 1.657 Lower Bound A Lower Bound of 2 6. Minimizing Average Flow Time on Unrelated Machines Minimizing Average Flow Time on Unrelated Machines Introduction Algorithm Step 1: The Linear Program Step 2: Preemptive SPT Step 3: Assignment of Jobs to Machines Step 4: Once More Preemptive SPT Analysis Refined Algorithm and Analysis Interval-Indexed LP Open Problems 7. Cooperation in Multiorganization Matching Cooperation in Multiorganization Matching Introduction The Multiorganization Assignment Problem Applications Related Work Contribution Complexity Results Computationally Hard Cases Polynomial Cases Approximation Generalizations Relaxation of the Selfishness of the Organizations General Graphs Conclusion 8. Randomized Algorithms for Buffer Management with 2-Bounded Delay Randomized Algorithms for Buffer Management with 2-Bounded Delay Introduction Related Work Our Contribution Preliminaries Lower Bound for 2-Bounded Sequences Lower Bound for 2-Uniform Sequences Upper Bound Computing Competitive Ratio Appendix 9. A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints A General Scheme for Designing Monotone Algorithms for Scheduling Problems with Precedence Constraints Introduction Previous Results Our Results The Class $C$ The General Scheme The Problem Q|prec,$r_{j}|C_{max}$ The Offline Problem Q|prec,$r_{j}|{\Sigma}w_{j}C_{j}$ 10. Malicious Bayesian Congestion Games Malicious Bayesian Congestion Games Introduction Model Congestion Games Malicious Bayesian Congestion Games Existence and Complexity of Pure Bayesian Nash Equilibria Price of Malice Conclusion and Open Problems 11. Stackelberg Strategies and Collusion in Network Games with Splittable Flow Stackelberg Strategies and Collusion in Network Games with Splittable Flow Introduction The Model Nonatomic Network Games with Coalitions Symmetric Load Balancing Games Multi-commodity Networks The Price of Anarchy for Restricted Latencies Stackelberg Strategies with Coalitional Followers Symmetric Load Balancing Games General Networks with a Single Follower SCALE Strategy with Multiple Followers Linear Latency Functions 12. Peak Shaving through Resource Buffering Peak Shaving through Resource Buffering Introduction Model and Preliminaries Offline Problem Battery Level Boundary Conditions Optimal Battery Size Online Problem Lower Bounds for $D -- R$ Bounded Battery Unbounded Battery and Boundary Conditions Conclusion 13. On Lagrangian Relaxation and Subset Selection Problems On Lagrangian Relaxation and Subset Selection Problems Introduction Subset Selection Problems Contribution Related Work Lagrangian Relaxation Technique Finding the Solutions s$_1$, s$_2$ Approximation Algorithms for Subset Selection Problems Unit Weights Arbitrary Weights Improving the Bounds via Enumeration Applications Budgeted Real Time Scheduling The Budgeted Generalized Assignment Problem Budgeted Maximum Weight Independent Set 14. Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements Introduction The Prize-Collecting Survivable Network Design Problem The Problem Definition Idea of the Algorithm Bounding the Edge Costs Penalty of the Solution and Its Total Cost The Prize-Collecting Forest Problem with General Connectivity Requirements (PCF-$\mathbb{Z}$) Definition and Formulation of the Problem Properties of the Penalty Function $\bar{\pi} (\bar{S})$ Algorithm Analysis for PCF-$\mathbb{Z}$ Algorithm The Performance Guarantee Proof of Theorem 1 Conclusions 15. Caching Content under Digital Rights Management Caching Content under Digital Rights Management Introduction Our Results Online DRM Overview and the Structure of This Paper Other Related Work Diminishing Cost Landlord The Online DRM Algorithm Simplifications The Online DRM Purchasing Strategy Injecting Cost Updates into the DCLL Sequence DRM -- Removing the Simplifying Assumptions Other Results 16. Reoptimization of Weighted Graph and Covering Problems Reoptimization of Weighted Graph and Covering Problems Introduction Preliminaries Maximum Weighted Independent Set Reoptimization of $WMIS$ with Edges Addition Reoptimization of $WMIS$ with Edges Removal Conclusions 17. Smoothing Imprecise 1.5D Terrains Smoothing Imprecise 1.5D Terrains Introduction Preliminaries Minimizing the Largest Turning Angle Properties of Optimal Terrains Solving the Subproblems Main Algorithm Correctness Analysis Maximizing the Smallest Turning Angle Minimizing and Maximizing the Total Turning Angle Discussion and Future Challenges 18. Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs Introduction Related Work Main Result Local 1+ $\epsilon$ Approximation Algorithm for Dominating Set Preliminaries Tiling of the Plane The Algorithm Local 1+ $\epsilon$ Approximation for Connected Dominating Set The Algorithm Proof of Correctness Conclusion 19. Dynamic Offline Conflict-Free Coloring for Unit Disks Dynamic Offline Conflict-Free Coloring for Unit Disks Introduction An Algorithm to Find a Dual CF-Coloring Modified Algorithm Using Min-Range Subset Dynamic Offline CF-Coloring for Unit Disks Dual CF-Coloring of $(C, RC)$ with $O(log n)$ Colors Dual CF-Coloring in a Unit Hexagon Remarks and Open Problems 20. Experimental Analysis of Scheduling Algorithms for Aggregated Links Experimental Analysis of Scheduling Algorithms for Aggregated Links Introduction FRFC Scheduling Algorithm Block Algorithm JBlock Experiments 21. A latex ss (2 symbol - c fraclog n n ) cs math (2 - c frac{log {n}}{n}) Approximation Algorithm for the Minimum Maximal Matching Problem A $(2 − c {log n}\over{n} )$ Approximation Algorithm for the Minimum Maximal Matching Problem Introduction Background Related Results Our Contribution Preliminaries Algorithm Finding $8c \log n$ Good Vertices $G'$ Construction Finding an Approximate Minimum Weighted Maximal Matching Performance Analysis Open Questions 22. On the Maximum Edge Coloring Problem subtitle (Extended Abstract) On the Maximum Edge Coloring Problem Introduction Notation and Preliminaries Bipartite Graphs Trees Complete Graphs Back matter
