Algorithms and Computation

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
3. Altmetric Badge
   Chapter 2 Adaptive Point Location in Planar Convex Subdivisions
4. Altmetric Badge
   Chapter 3 Competitive Local Routing with Constraints
5. Altmetric Badge
   Chapter 4 Navigating Weighted Regions with Scattered Skinny Tetrahedra
6. Altmetric Badge
   Chapter 5 On the Succinct Representation of Unlabeled Permutations
7. Altmetric Badge
   Chapter 6 How to Select the Top k Elements from Evolving Data?
8. Altmetric Badge
   Chapter 7 Optimal Search Trees with 2-Way Comparisons
9. Altmetric Badge
   Chapter 8 Multidimensional Range Selection
10. Altmetric Badge
    Chapter 9 On the Minimum Cost Range Assignment Problem
11. Altmetric Badge
    Chapter 10 On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems
12. Altmetric Badge
    Chapter 11 General Caching Is Hard: Even with Small Pages
13. Altmetric Badge
    Chapter 12 The Secretary Problem with a Choice Function
14. Altmetric Badge
    Chapter 13 The Benefit of Recombination in Noisy Evolutionary Search
15. Altmetric Badge
    Chapter 14 Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples
16. Altmetric Badge
    Chapter 15 Obtaining a Triangular Matrix by Independent Row-Column Permutations
17. Altmetric Badge
    Chapter 16 Many-to-one Matchings with Lower Quotas: Algorithms and Complexity
18. Altmetric Badge
    Chapter 17 Minimizing the Maximum Moving Cost of Interval Coverage
19. Altmetric Badge
    Chapter 18 Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
20. Altmetric Badge
    Chapter 19 Unbounded Discrepancy of Deterministic Random Walks on Grids
21. Altmetric Badge
    Chapter 20 Trading off Worst and Expected Cost in Decision Tree Problems
22. Altmetric Badge
    Chapter 21 Sliding Token on Bipartite Permutation Graphs
23. Altmetric Badge
    Chapter 22 Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
24. Altmetric Badge
    Chapter 23 Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
25. Altmetric Badge
    Chapter 24 Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
26. Altmetric Badge
    Chapter 25 Geometric Matching Algorithms for Two Realistic Terrains
27. Altmetric Badge
    Chapter 26 Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability
28. Altmetric Badge
    Chapter 27 The 2-Center Problem in a Simple Polygon
29. Altmetric Badge
    Chapter 28 Choice Is Hard
30. Altmetric Badge
    Chapter 29 Fully Dynamic Betweenness Centrality
31. Altmetric Badge
    Chapter 30 When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots
32. Altmetric Badge
    Chapter 31 Cops and Robbers on String Graphs
33. Altmetric Badge
    Chapter 32 Min-Power Covering Problems
34. Altmetric Badge
    Chapter 33 Minimizing the Diameter of a Spanning Tree for Imprecise Points
35. Altmetric Badge
    Chapter 34 Model-Based Classification of Trajectories
36. Altmetric Badge
    Chapter 35 Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
37. Altmetric Badge
    Chapter 36 Unfolding Orthogonal Polyhedra with Linear Refinement
38. Altmetric Badge
    Chapter 37 Colored Non-crossing Euclidean Steiner Forest
39. Altmetric Badge
    Chapter 38 On a generalization of Nemhauser and Trotter's local optimization theorem
40. Altmetric Badge
    Chapter 39 Approximation Algorithms in the Successive Hitting Set Model
41. Altmetric Badge
    Chapter 40 Generating Random Hyperbolic Graphs in Subquadratic Time
42. Altmetric Badge
    Chapter 41 Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
43. Altmetric Badge
    Chapter 42 Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
44. Altmetric Badge
    Chapter 43 An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
45. Altmetric Badge
    Chapter 44 Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
46. Altmetric Badge
    Chapter 45 Algorithms and Computation
47. Altmetric Badge
    Chapter 46 The VC-Dimension of Visibility on the Boundary of a Simple Polygon
48. Altmetric Badge
    Chapter 47 Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)
49. Altmetric Badge
    Chapter 48 Effectiveness of Structural Restrictions for Hybrid CSPs
50. Altmetric Badge
    Chapter 49 Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
51. Altmetric Badge
    Chapter 50 Quantum Algorithm for Triangle Finding in Sparse Graphs
52. Altmetric Badge
    Chapter 51 On Hardness of the Joint Crossing Number
53. Altmetric Badge
    Chapter 52 An $$O(n^{\epsilon })$$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
54. Altmetric Badge
    Chapter 53 Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
55. Altmetric Badge
    Chapter 54 Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
56. Altmetric Badge
    Chapter 55 A New Approximate Min-Max Theorem with Applications in Cryptography
57. Altmetric Badge
    Chapter 56 Give Me Another One!
58. Altmetric Badge
    Chapter 57 On the Complexity of Computing Prime Tables
59. Altmetric Badge
    Chapter 58 Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
60. Altmetric Badge
    Chapter 59 Run Generation Revisited: What Goes Up May or May Not Come Down
61. Altmetric Badge
    Chapter 60 Streaming Verification in Data Analysis
62. Altmetric Badge
    Chapter 61 All-Around Near-Optimal Solutions for the Online Bin Packing Problem
63. Altmetric Badge
    Chapter 62 Serving Online Requests with Mobile Servers
64. Altmetric Badge
    Chapter 63 An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
65. Altmetric Badge
    Chapter 64 Inferring Strings from Full Abelian Periods
66. Altmetric Badge
    Chapter 65 Toehold DNA Languages are Regular (Extended Abstract)