Algorithms - ESA 2014

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Losing Weight by Gaining Edges
3. Altmetric Badge
   Chapter 2 Optimal Coordination Mechanisms for Multi-job Scheduling Games
4. Altmetric Badge
   Chapter 3 Theory and Practice of Chunked Sequences
5. Altmetric Badge
   Chapter 4 Convex Hulls under Uncertainty
6. Altmetric Badge
   Chapter 5 The Space-Stretch-Time Tradeoff in Distance Oracles
7. Altmetric Badge
   Chapter 6 Distribution-Sensitive Construction of the Greedy Spanner
8. Altmetric Badge
   Chapter 7 Recognizing Shrinkable Complexes Is NP-Complete
9. Altmetric Badge
   Chapter 8 Improved Approximation Algorithms for Box Contact Representations
10. Altmetric Badge
    Chapter 9 Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
11. Altmetric Badge
    Chapter 10 The Batched Predecessor Problem in External Memory
12. Altmetric Badge
    Chapter 11 Polynomial Decompositions in Polynomial Time
13. Altmetric Badge
    Chapter 12 Fault-Tolerant Approximate Shortest-Path Trees
14. Altmetric Badge
    Chapter 13 Fast Witness Extraction Using a Decision Oracle
15. Altmetric Badge
    Chapter 14 Complexity of Higher-Degree Orthogonal Graph Embedding in the Kandinsky Model
16. Altmetric Badge
    Chapter 15 A Subexponential Parameterized Algorithm for Proper Interval Completion
17. Altmetric Badge
    Chapter 16 Computing Persistent Homology with Various Coefficient Fields in a Single Pass
18. Altmetric Badge
    Chapter 17 De-anonymization of Heterogeneous Random Graphs in Quasilinear Time
19. Altmetric Badge
    Chapter 18 Competitive Algorithms for Restricted Caching and Matroid Caching
20. Altmetric Badge
    Chapter 19 Improved Algorithms for Resource Allocation under Varying Capacity
21. Altmetric Badge
    Chapter 20 Nearly Tight Approximability Results for Minimum Biclique Cover and Partition
22. Altmetric Badge
    Chapter 21 Succinct Indices for Path Minimum, with Applications to Path Reporting
23. Altmetric Badge
    Chapter 22 Online Bipartite Matching with Decomposable Weights
24. Altmetric Badge
    Chapter 23 A Faster Algorithm for Computing Straight Skeletons
25. Altmetric Badge
    Chapter 24 Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
26. Altmetric Badge
    Chapter 25 Cache-Oblivious Persistence
27. Altmetric Badge
    Chapter 26 Lightweight Approximate Selection
28. Altmetric Badge
    Chapter 27 Robust Distance Queries on Massive Networks
29. Altmetric Badge
    Chapter 28 A Dynamic Data Structure for MSO Properties in Graphs with Bounded Tree-Depth
30. Altmetric Badge
    Chapter 29 Large Independent Sets in Triangle-Free Planar Graphs
31. Altmetric Badge
    Chapter 30 GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem
32. Altmetric Badge
    Chapter 31 Switching Colouring of G ( n , d / n ) for Sampling up to Gibbs Uniqueness Threshold
33. Altmetric Badge
    Chapter 32 From Graph to Hypergraph Multiway Partition: Is the Single Threshold the Only Route?
34. Altmetric Badge
    Chapter 33 Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
35. Altmetric Badge
    Chapter 34 Bicriteria Data Compression: Efficient and Usable
36. Altmetric Badge
    Chapter 35 Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
37. Altmetric Badge
    Chapter 36 LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
38. Altmetric Badge
    Chapter 37 Representative Sets of Product Families
39. Altmetric Badge
    Chapter 38 Weighted Ancestors in Suffix Trees
40. Altmetric Badge
    Chapter 39 Improved Practical Matrix Sketching with Guarantees
41. Altmetric Badge
    Chapter 40 Computing Regions Decomposable into m Stars
42. Altmetric Badge
    Chapter 41 The Parameterized Complexity of Graph Cyclability
43. Altmetric Badge
    Chapter 42 Dimension Reduction via Colour Refinement
44. Altmetric Badge
    Chapter 43 How Experts Can Solve LPs Online
45. Altmetric Badge
    Chapter 44 Parameterized Complexity of the k -Arc Chinese Postman Problem
46. Altmetric Badge
    Chapter 45 Approximating the Maximum Overlap of Polygons under Translation
47. Altmetric Badge
    Chapter 46 Ordering without Forbidden Patterns
48. Altmetric Badge
    Chapter 47 Halving Balls in Deterministic Linear Time
49. Altmetric Badge
    Chapter 48 Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
50. Altmetric Badge
    Chapter 49 Optimal Parallel Quantum Query Algorithms
51. Altmetric Badge
    Chapter 50 Sublinear Space Algorithms for the Longest Common Substring Problem
52. Altmetric Badge
    Chapter 51 Nested Set Union
53. Altmetric Badge
    Chapter 52 Improved Explicit Data Structures in the Bitprobe Model
54. Altmetric Badge
    Chapter 53 Deeper Local Search for Better Approximation on Maximum Internal Spanning Trees
55. Altmetric Badge
    Chapter 54 FPTAS for Counting Weighted Edge Covers
56. Altmetric Badge
    Chapter 55 Solving Multicut Faster Than 2 n
57. Altmetric Badge
    Chapter 56 Tight Bounds for Active Self-assembly Using an Insertion Primitive
58. Altmetric Badge
    Chapter 57 Trace Reconstruction Revisited
59. Altmetric Badge
    Chapter 58 PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies
60. Altmetric Badge
    Chapter 59 Polynomial-Time Approximation Schemes for Circle Packing Problems
61. Altmetric Badge
    Chapter 60 Document Retrieval on Repetitive Collections
62. Altmetric Badge
    Chapter 61 An Improved Analysis of the Mömke-Svensson Algorithm for Graph-TSP on Subquartic Graphs
63. Altmetric Badge
    Chapter 62 The Input/Output Complexity of Sparse Matrix Multiplication
64. Altmetric Badge
    Chapter 63 Faster FPTASes for Counting and Random Generation of Knapsack Solutions
65. Altmetric Badge
    Chapter 64 Improved Guarantees for Tree Cut Sparsifiers
66. Altmetric Badge
    Chapter 65 Representative Families: A Unified Tradeoff-Based Approach
67. Altmetric Badge
    Chapter 66 A Branch and Price Procedure for the Container Premarshalling Problem
68. Altmetric Badge
    Chapter 67 Space-Efficient Randomized Algorithms for K-SUM
69. Altmetric Badge
    Chapter 68 Equivalence between Priority Queues and Sorting in External Memory
70. Altmetric Badge
    Chapter 69 Amortized Bounds for Dynamic Orthogonal Range Reporting