Approximation and Online Algorithms
Springer International Publishing (Verlag)
978-3-030-04692-7 (ISBN)
The 19 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 44 submissions. Topics of interest for WAOA 2016 were: graph algorithms; inapproximability results; network design; packing and covering; paradigms for the design and analysis of approximation and online algorithms; parameterized complexity; scheduling problems; algorithmic game theory; algorithmic trading; coloring and partitioning; competitive analysis; computational advertising; computational finance; cuts and connectivity; geometric problems; mechanism design; resource augmentation; and real-world applications.
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.- Reconfigurationof Graphs with Connectivity Constraints.- The Itinerant List Update Problem.- The Price of Fixed Assignments in Stochastic Extensible Bin Packing.
| Erscheinungsdatum | 30.11.2018 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | X, 349 p. 39 illus., 22 illus. in color. |
| Verlagsort | Cham |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 551 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Schlagworte | Algorithm analysis and problem complexity • Applications • approximation algorithms • competitive ratio • Computer Networks • Computer Science • conference proceedings • data structures • graph theory • Informatics • On-line Algorithms • Probability • Problem Solving • Research • set theory • Telecommunication networks • telecommunication traffic |
| ISBN-10 | 3-030-04692-3 / 3030046923 |
| ISBN-13 | 978-3-030-04692-7 / 9783030046927 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
