Approximation and Online Algorithms

“Almost Stable” Matchings in the Roommates Problem.- On the Minimum Load Coloring Problem.- Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT.- The Hardness of Network Design for Unsplittable Flow with Selfish Users.- Improved Approximation Algorithm for Convex Recoloring of Trees.- Exploiting Locality: Approximating Sorting Buffers.- Approximate Fair Cost Allocation in Metric Traveling Salesman Games.- Rounding of Sequences and Matrices, with Applications.- A Note on Semi-online Machine Covering.- SONET ADMs Minimization with Divisible Paths.- The Conference Call Search Problem in Wireless Networks.- Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents.- Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost.- A Better-Than-Greedy Algorithm for k-Set Multicover.- Deterministic Online Optical Call Admission Revisited.- Scheduling Parallel Jobs with Linear Speedup.- Online Removable Square Packing.- The Online Target Date Assignment Problem.- Approximation and Complexity of k–Splittable Flows.- On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem.- Tighter Approximations for Maximum Induced Matchings in Regular Graphs.- On Approximating Restricted Cycle Covers.- A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs.- Speed Scaling of Tasks with Precedence Constraints.- Partial Multicuts in Trees.- Approximation Schemes for Packing with Item Fragmentation.