Preface
Organization
Abstracts of Invited Talks
Adjacency Labelling of Planar Graphs (and Beyond)
Algorithms for Explainable Clustering
Contents
On the Spanning and Routing Ratios of the Directed 6-Graph
1 Introduction
1.1 Our Contributions
2 Preliminaries
2.1 The Routing Model
3 Upper Bound on the Spanning Ratio
4 Routing Algorithm and Upper Bound on Routing Ratio
5 Conclusions
References
The Minimum Moving Spanning Tree Problem
1 Introduction
2 Preliminaries
2.1 Definitions
2.2 Convexity
3 Minimum Bottleneck Moving Spanning Tree
4 Minimum Moving Spanning Tree
4.1 A 2-approximation Algorithm
4.2 An O(n logn)-time (2+)-approximation Algorithm
4.3 NP-hardness of MMST
References
Scheduling with Testing on Multiple Identical Parallel Machines
1 Introduction
1.1 Related Work
1.2 Contribution
1.3 Preliminary Definitions
2 Non-preemptive Setting
2.1 Lower Bound and Greedy Algorithm
2.2 SBS Algorithm
2.3 An Improved Algorithm for the Uniform Case
3 Results with Preemption
4 Conclusion
References
Online Makespan Minimization with Budgeted Uncertainty
1 Introduction
2 Problem Definition
3 Graham's Greedy Strategy
3.1 Upper Bound
3.2 Lower Bound
4 An Improved Deterministic Algorithm
4.1 Deterministic Lower Bounds
References
Pattern Matching in Doubling Spaces
1 Introduction
2 Notation and Preliminary
3 Reduction from k-Clique
4 Approximation Algorithm for the -Distortion Problem
References
Reachability Problems for Transmission Graphs
1 Introduction
2 Improved Algorithm for Computing a t-Spanner
2.1 Theta Graphs and t-Spanners of Transmission Graphs
2.2 Efficient Algorithm for Computing the t-Spanner
3 Reachability Oracle for Unbounded Radius Ratio
3.1 Chain
3.2 Separation Tree of R
3.3 Chain Indices
3.4 Reachability Oracles
4 Continuous Reachability Oracle
References
On Minimum Generalized Manhattan Connections
1 Introduction
1.1 Our Contributions
1.2 Overview of Techniques
1.3 Outlook and Open Problems
2 Model and Preliminaries
3 NP-Hardness
4 An Approximation Algorithm for s-Thin Instances
5 A Sublogarithmic Approximation Algorithm
References
HalftimeHash: Modern Hashing Without 64-Bit Multipliers or Finite Fields
1 Introduction
1.1 Portability
1.2 Prior Almost-Universal Families
1.3 Outline
2 Notations and Conventions
3 Prior Work
3.1 Tree Hash
3.2 NH
3.3 Encode, Hash, Combine
4 Generalized EHC
5 Implementation
5.1 EHC
5.2 Tree Hash
6 Performance
6.1 Analysis
6.2 Cumulative Analysis
6.3 Benchmarks
7 Future Work
References
Generalized Disk Graphs
1 Introduction
2 Geometric Representation
3 Approximation Scheme for Weighted Independent Sets
4 Structural Properties
5 One-Dimensional Case
6 Conclusion and Open Questions
References
A 4-Approximation of the 23-MST
1 Introduction
2 Preliminaries
3 Replacing an Arbitrary Path by a 23-Tree
3.1 Phase I
3.2 Phase II
3.3 Phase III
3.4 Correctness
4 Conclusion
References
Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations
1 Introduction
1.1 Results
1.2 Related Work
1.3 Paper Organization
2 Preliminaries
2.1 The Model
3 Dictionary for Multisets via Key-Value Dictionaries (Sparse Case)
4 Dictionary for Multisets (Dense Case)
4.1 Parametrization
4.2 Hash Functions
4.3 The First Level of the Multiset Dictionary
4.4 The Spare
4.5 Overflow Analysis
4.6 Space Analysis
References
The Neighborhood Polynomial of Chordal Graphs
1 Introduction
2 Preliminaries
3 Algorithm for Chordal Graphs
4 Complexity of the Anchor Width
5 Discussion
References
Incomplete Directed Perfect Phylogeny in Linear Time
1 Introduction
2 Preliminaries
2.1 Preliminary Results
3 (N,N)-DC in O(N2logN) Total Update Time and O(N) Time per Query
4 (N,N)-DC in O(N2) Total Update Time and O(N) Time per Query
References
Euclidean Maximum Matchings in the PlaneβLocal to Global
1 Introduction
1.1 Our Contributions
1.2 Some Related Works
2 A Lower Bound for k-Local Maximum Matchings
3 Better Lower Bound for 3-Local Maximum Matchings
4 Better Lower Bound for 2-Local Maximum Matchings
5 Pairwise-Crossing Matchings are Globally Maximum
6 Discussion
References
Solving Problems on Generalized Convex Graphs via Mim-Width
1 Introduction
2 The Proof of Theorem 1
3 The Proof of Theorem 2
4 The Proof of Theorem 3
5 A Refined Parameter Analysis and Final Remarks
References
Improved Bounds on the Spanning Ratio of the Theta-5-Graph
1 Introduction
2 Preliminaries
3 Analysis
4 Proving a Spanning Ratio of 5.70
4.1 Proof of Lemma 13
4.2 Proof of Lemma 15
References
Computing Weighted Subset Transversals in H-Free Graphs
1 Introduction
2 Preliminaries
3 General Framework of the Polynomial Algorithms
4 Applying Our Framework on (3P1+P2)-Free Graphs
5 Conclusions
References
Computing the FrΓ©chet Distance Between Uncertain Curves in One Dimension
1 Introduction
2 Preliminaries
3 Lower Bound FrΓ©chet Distance in One Dimension
4 Upper Bound FrΓ©chet Distance
5 Weak FrΓ©chet Distance
5.1 Algorithm for Continuous Setting
5.2 Hardness of Discrete Setting
References
Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
1 Introduction
2 Preliminaries
3 Previous Geometric Observations
4 New Algorithm
4.1 Interaction Between Two Standard Lists
4.2 Interaction Between a Standard List and a Hereditary List
4.3 Putting Things Together
References
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
1 Introduction
2 Preliminaries
3 Cycle-Trees and Proof of Theorem 1
3.1 3-Connected Instances
3.2 2-Connected and 1-Connected Instances
4 Nested Pseudotrees
5 Conclusions and Open Problems
References
An APTAS for Bin Packing with Clique-Graph Conflicts
1 Introduction
1.1 Contribution and Techniques
1.2 Related Work
2 Preliminaries: Scheduling with Bag Constraints
3 An APTAS for GBP
3.1 Rounding of Large and Medium Items
3.2 Large and Medium Items
3.3 Small Items
3.4 Putting It All Together
References
Fast Deterministic Algorithms for Computing All Eccentricities in (Hyperbolic) Helly Graphs
1 Introduction
2 Helly Graphs and Their Hyperbolicity
3 All Eccentricities in Helly Graphs
4 Eccentricities in Helly Graphs with Small Hyperbolicity
4.1 Proof of Lemma 6
References
ANN for Time Series Under the FrΓ©chet Distance
1 Introduction
1.1 Previous Work
1.2 Known Techniques
1.3 Preliminaries
1.4 Our Contributions
1.5 Signatures
2 A Constant-Factor Approximation for Time Series
3 Improving the Approximation Factor to (2+)
4 An 3Μ942"Μ613A``4547`"603AO(k)-ANN Data Structure with Near-Linear Space
5 A Lower Bound in the Cell-Probe Model
6 Conclusions
References
Strictly In-Place Algorithms for Permuting and Inverting Permutations
1 Introduction
2 Preliminaries
3 Leader Election in Smaller Space
4 Inverting Permutations in Smaller Space
References
A Stronger Lower Bound on Parametric Minimum Spanning Trees
1 Introduction
2 Background and Preliminaries
3 Replacing Edges by Triangles
4 Weighted 2-Trees
5 Packing into Dense Graphs
6 Conclusions
References
Online Bin Packing of Squares and Cubes
1 Introduction
2 Algorithm Extended Harmonic (EH)
3 Weighting Functions and Results
3.1 Upper Bounds on the Asymptotic Competitive Ratio
References
Exploration of k-Edge-Deficient Temporal Graphs
1 Introduction
2 Preliminaries
3 O(kn logn)-Time Exploration of k-Edge-Deficient Temporal Graphs
4 Linear-Time Exploration of 1-Edge-Deficient Temporal Graphs
5 Lower Bound
6 Conclusion
References
Parameterized Complexity of Categorical Clustering with Size Constraints
1 Introduction
2 Preliminaries
3 FPT Algorithm for Parameterization by B
4 Clustering with Size Constraints
5 Conclusion
References
Graph Pricing with Limited Supply
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Organization
2 Preliminaries
3 Local-Search Algorithms
3.1 Single-Swap Analysis
3.2 An Improved Multi-swap Algorithm for Bounded Capacities
3.3 Proof of Theorem 5
4 LP-Based Approximations
4.1 Proof Sketch for Theorem 4
A Reduction to L-Pricing
References
Fair Correlation Clustering with Global and Local Guarantees
1 Introduction
1.1 Our Results
1.2 Organization
2 Fair Correlation Clustering
2.1 6.18-Approximation Algorithm
2.2 Analysis of 6.18-Approximation Algorithm
2.3 Towards a 5.5-Approximation Algorithm
3 Local Fair Correlation Clustering
3.1 Analysis of Algorithm 2
References
Better Distance Labeling for Unweighted Planar Graphs
1 Introduction
2 Previous Scheme
3 Improved Scheme
4 Efficient Decoding
References
How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths
1 Introduction
2 Structural Properties
3 H-Minor-Free Graphs
4 General Graphs
References
Algorithms for Radius-Optimally Augmenting Trees in a Metric Space
1 Introduction
1.1 Our Approach
2 Preliminaries
3 An O(nlogn) Expected Time Algorithm for the Discrete ROAT problem
3.1 Case 1: The Center Lies on P
3.2 Case 2: The Center Does Not Lie on P
4 A Linear Time Algorithm for Continuous ROAT
4.1 Simplify the ROAWP Problem
4.2 Solve ROAMWP in Linear Time
References
Upper and Lower Bounds for Fully Retroactive Graph Problems
1 Introduction
2 Preliminaries
3 Lower Bounds
4 Incremental Fully Retroactive Connectivity and SF
5 Fully Retroactive Data Structures
References
Characterization of Super-Stable Matchings
1 Introduction
1.1 Related Works
2 Preliminaries
3 Irreducible Super-Stable Matchings
4 A Maximal Sequence of Super-Stable Matchings
4.1 Correctness of Algorithm2
4.2 Running Time of Algorithm2
4.3 Rotation Poset
5 The Super-Stable Matching Polytope
5.1 Partial Order Preference Lists
5.2 The Strongly Stable Matching Polytope
References
Uniform Embeddings for Robinson Similarity Matrices
1 Introduction
1.1 Related Works
2 Uniform Embeddings
3 Bounds, Walks, and Their Concatenation
4 A Sufficient and Necessary Condition
4.1 Cycles and Paths
4.2 Finding a Uniform Embedding
5 Testing the Condition
5.1 A Partial Order on Bounds
5.2 Generating the Bounds
5.3 A Combinatorial Algorithm for the Case k=2
6 Conclusions
References
Particle-Based Assembly Using Precise Global Control
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Preliminaries
3 NP-Hardness of 3D-STAP
4 Optimization Variant and Approximation
5 Efficient Algorithms for Special Classes
5.1 Tree Shapes
5.2 Scaled Shapes
6 Conclusion and Future Work
References
Independent Sets in Semi-random Hypergraphs
1 Introduction
1.1 Our Models and Results
1.2 Related Work
1.3 Preliminaries and Notation
1.4 Proof Overview
2 Bounding the Contribution from the Random Hypergraph
3 Algorithm for Computing a Large Independent Set
References
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
1 Introduction
1.1 Graph Theory
1.2 Query Complexity
2 Result
2.1 Breadth-First Search Subroutine
2.2 Depth-First Search Subroutine
3 Conclusion
References
Support Optimality and Adaptive Cuckoo Filters
1 Introduction
1.1 Results
2 Three Adaptive Cuckoo Filters
2.1 ACF Parameters and Internal State
2.2 Cuckoo Filter Operations
2.3 Cuckooing ACF
2.4 Cyclic ACF
2.5 Swapping ACF
3 Bounding the False Positive Rate by the Number of Distinct Queries
3.1 Proof Sketch of Theorem 1
4 Experiments
4.1 Experimental Results
5 Adversarial Adaptivity
5.1 Definition
5.2 Lower Bounds
References
Computing the Union Join and Subset Graph of Acyclic Hypergraphs in Subquadratic Time
1 Introduction
1.1 Acyclic Hypergraphs
1.2 Union Join Graph
1.3 Subset Graph
1.4 Our Contribution
2 Preliminaries
3 -Acyclic Hypergraphs
3.1 Hardness Results
3.2 Union Join Graph via Subset Graph
4 Subclasses of Acyclic Hypergraphs
4.1 -Acyclic Hypergraphs
4.2 -Acyclic Hypergraphs
4.3 Interval Hypergraphs
References
Algorithms for the Line-Constrained Disk Coverage and Related Problems
1 Introduction
1.1 Related Work
1.2 Our Approach
2 Preliminaries
3 The L and L2 Cases
3.1 An Algorithmic Scheme for L and L2 Metrics
3.2 The L Metric
3.3 The L2 Metric
References
A Universal Cycle for Strings with Fixed-Content (Which Are Also Known as Multiset Permutations)
1 Introduction
2 Preliminaries
2.1 Necklaces with Fixed-Content
2.2 Cool-Lex Order
2.3 Necklace-Prefix Algorithm
3 Recursive Algorithm
4 Constructing a Shorthand Universal Cycle for Fixed-Content
4.1 Efficiency
References
Routing on Heavy-Path WSPD-Spanners
1 Introduction
1.1 Compressed Quadtrees
1.2 The Well-Separated Pair Decomposition
2 The Heavy Path WSPD Spanner
2.1 Constructing a Heavy Path WSPD Spanner
3 Local Routing in Euclidean Space
3.1 Routing Tables
3.2 Routing in a Heavy Path WSPD Spanner
3.3 Analysis of the Local Routing Algorithm
4 Conclusions
References
Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance
1 Introduction
2 Input Regions are Points
3 Input Regions are Convex -fat Regions
4 Input Regions are Convex Regions
5 Input Regions are General Regions
5.1 Two Regions
5.2 Three or More Regions
6 Conclusion
References
Diverse Partitions of Colored Points
1 Introduction
2 Related Work
3 Convex Versus Voronoi Partitions in 1D
4 Diverse Voronoi Partition in 1D
4.1 NP-Hardness When Richness is the Diversity Measure
4.2 NP-Hardness When Shannon Index is the Diversity Measure
4.3 Polynomial-Time Solution for Discrete Candidate Sites
5 Approximation for Diverse Voronoi Partition in 1D
6 Diverse Convex Partition is NP-Hard in 2D
7 Conclusions
References
Reverse Shortest Path Problem for Unit-Disk Graphs
1 Introduction
1.1 Related Work
1.2 Our Approach
2 Preliminaries
3 The First Algorithm
3.1 Building the Grid
3.2 Running BFS
4 The Second Algorithm
5 Concluding Remarks
References
Author Index