Approximation and Online Algorithms: 16th International Workshop, Waoa 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers

ISBN-13: 9783030046927 / Angielski / Miękka / 2018 / 349 str.

Leah Epstein; Thomas Erlebach

Spis treści

Some Easy and Some Not So Easy Geometric Optimization Problems.- Deterministic Min-Cost Matching with Delays.- Sequential Metric Dimension.- A Primal-Dual Online Deterministic Algorithm for Matching with Delays.- Advice Complexity of Priority Algorithms.- Approximating Node-Weighted k-MST on Planar Graphs.- Exploring Sparse Graphs with Advice.- Call Admission Problems on Grids with Advice.- Improved Approximation Algorithms for Minimum Power Covering Problems.- DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals.- Strategic Contention Resolution in Multiple Channels.- Sublinear Graph Augmentation for Fast Query Implementation.- Bin Packing Games with Weight Decision: How To Get a Small Value for the Price of Anarchy.- Probabilistic Embeddings of the Fréchet Distance.- Algorithms for Dynamic NFV Workload.- Longest Increasing Subsequence under Persistent Comparison Errors.- Cut Sparsifiers for Balanced Digraphs.- Reconfiguration of Graphs with Connectivity Constraints.- The Itinerant List Update Problem.- The Price of Fixed Assignments in Stochastic Extensible Bin Packing.