Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings

Front Matter....Pages I-XXII
Front Matter....Pages 1-1
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino....Pages 3-13
Adaptive Point Location in Planar Convex Subdivisions....Pages 14-22
Competitive Local Routing with Constraints....Pages 23-34
Navigating Weighted Regions with Scattered Skinny Tetrahedra....Pages 35-45
Front Matter....Pages 47-47
On the Succinct Representation of Unlabeled Permutations....Pages 49-59
How to Select the Top k Elements from Evolving Data?....Pages 60-70
Optimal Search Trees with 2-Way Comparisons....Pages 71-82
Multidimensional Range Selection....Pages 83-92
Front Matter....Pages 93-93
On the Minimum Cost Range Assignment Problem....Pages 95-105
On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems....Pages 106-115
General Caching Is Hard: Even with Small Pages....Pages 116-126
Front Matter....Pages 127-127
The Secretary Problem with a Choice Function....Pages 129-139
The Benefit of Recombination in Noisy Evolutionary Search....Pages 140-150
Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples....Pages 151-162
Front Matter....Pages 163-163
Obtaining a Triangular Matrix by Independent Row-Column Permutations....Pages 165-175
Many-to-one Matchings with Lower Quotas: Algorithms and Complexity....Pages 176-187
Minimizing the Maximum Moving Cost of Interval Coverage....Pages 188-198
Front Matter....Pages 199-199
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions....Pages 201-211
Unbounded Discrepancy of Deterministic Random Walks on Grids....Pages 212-222
Trading off Worst and Expected Cost in Decision Tree Problems....Pages 223-234
Front Matter....Pages 235-235
Sliding Token on Bipartite Permutation Graphs....Pages 237-247
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width....Pages 248-258
Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms....Pages 259-270
Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs....Pages 271-282
Front Matter....Pages 283-283
Geometric Matching Algorithms for Two Realistic Terrains....Pages 285-295
Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability....Pages 296-306
The 2-Center Problem in a Simple Polygon....Pages 307-317
Choice Is Hard....Pages 318-328
Front Matter....Pages 329-329
Fully Dynamic Betweenness Centrality....Pages 331-342
When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots....Pages 343-354
Cops and Robbers on String Graphs....Pages 355-366
Min-Power Covering Problems....Pages 367-377
Front Matter....Pages 379-379
Minimizing the Diameter of a Spanning Tree for Imprecise Points....Pages 381-392
Model-Based Classification of Trajectories....Pages 393-403
Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures....Pages 404-414
Unfolding Orthogonal Polyhedra with Linear Refinement....Pages 415-425
Front Matter....Pages 427-427
Colored Non-crossing Euclidean Steiner Forest....Pages 429-441
On a Generalization of Nemhauser and Trotter’s Local Optimization Theorem....Pages 442-452
Approximation Algorithms in the Successive Hitting Set Model....Pages 453-464
Front Matter....Pages 465-465
Generating Random Hyperbolic Graphs in Subquadratic Time....Pages 467-478
Front Matter....Pages 465-465
Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing....Pages 479-490
Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty....Pages 491-501
Front Matter....Pages 503-503
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings....Pages 505-516
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds....Pages 517-528
Computing the Gromov-Hausdorff Distance for Metric Trees....Pages 529-540
The VC-Dimension of Visibility on the Boundary of a Simple Polygon....Pages 541-551
Front Matter....Pages 553-553
Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)....Pages 555-565
Effectiveness of Structural Restrictions for Hybrid CSPs....Pages 566-577
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions....Pages 578-589
Quantum Algorithm for Triangle Finding in Sparse Graphs....Pages 590-600
Front Matter....Pages 601-601
On Hardness of the Joint Crossing Number....Pages 603-613
Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions....Pages 614-624
Front Matter....Pages 625-636
A New Approximate Min-Max Theorem with Applications in Cryptography....Pages 637-649
Give Me Another One!....Pages 651-651
On the Complexity of Computing Prime Tables....Pages 653-663
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games....Pages 664-676
Front Matter....Pages 677-688
Run Generation Revisited: What Goes Up May or May Not Come Down....Pages 689-699
Streaming Verification in Data Analysis....Pages 701-701
Front Matter....Pages 703-714
All-Around Near-Optimal Solutions for the Online Bin Packing Problem....Pages 715-726
Serving Online Requests with Mobile Servers....Pages 701-701
Front Matter....Pages 727-739
An In-place Framework for Exact and Approximate Shortest Unique Substring Queries....Pages 740-751
Inferring Strings from Full Abelian Periods....Pages 753-753
Toehold DNA Languages are Regular (Extended Abstract)....Pages 755-767
Back Matter....Pages 768-779
....Pages 780-790