Algorithms - ESA 2015

Name: Algorithms - ESA 2015 | 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings

Nikhil Bansal Irene Finocchi(Editor)

Springer (Publisher)

Published on 1. September 2015

XXIII, 1053 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-48350-3 (ISBN)

€96.29incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
Organization
Invited Lectures
Correlated Locality-Sensitive Hashing
On the Discrete Dynamics of Probabilistic (Finite) Population Protocols
Contents
Improved Approximation Algorithms for Stochastic Matching
1 Introduction
1.1 Our Results
1.2 Related Work
2 Stochastic Matching
2.1 Bipartite Graphs
2.2 General Graphs
3 Online Stochastic Matching with Timeouts
Sorting and Permuting without Bank Conflicts on GPUs
1 Introduction
2 Sorting and Partitioning
3 A Randomized Algorithm for Permutation
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons
1 Introduction
2 The Algorithm
3 Convex Containers
Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for GeneralizedFlow Time Problems
1 Introduction
2 Linear Programming Relaxation
3 A Primal-Dual Interpretation of HDF for j wjFj
4 A Framework for Primal-Dual Algorithms
5 A Generalized Framework Using Dual-Fitting
5.1 Online GFP with General Cost Functions and Equal-Density Jobs
5.2 Online GFP with Concave Cost Functions
6 Conclusion
Buffer Management for Packets with Processing Times
1 Introduction
Our Contributions - Job Scheduling.
Our Contributions - Buffer Management.
Related Work.
Model Description.
2 Job Scheduling
3 Buffer Management
3.1 Packets with Unit Values
3.2 Packets with Constant Density
3.3 Arbitrary Value and Processing Requirement
A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem
1 Introduction
2 IP Formulation and Complexity
3 Mathematical Foundations of the Problem
Unimodularity in Submatrices of ¶
Existence of Non-trivial Solutions
4 A Triplet-Based Branch and Bound Algorithm
5 Column Generation Approaches
6 Computational Results
7 Conclusions
Exact Minkowski Sums of Polygons With Holes
1 Introduction
1.1 Terminology and Related Work
1.2 Our Results
2 Filtering Out Holes
3 Implementation
3.1 Reduced Convolution
3.2 Decomposition
4 Experiments
5 Conclusion
? & 4*
1 Introduction
2 Twisted Cylinders
3 Method
4 Sequential Runs
5 Computing ?27
6 Validity and Certification
7 Conclusion
Revenue Maximization for Selling Multiple Correlated Items
1 Introduction
2 Related Work
3 Results and Techniques
4 Preliminaries
5 The Core Decomposition Technique
6 Semi-independent Distributions
7 Common Base-Value Distributions
Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
1 Introduction
2 Preliminaries and Related Work
2.1 Sequential Max-Flow and Min-Cut Computations
2.2 Parallel and Distributed Approaches to the Problem
3 A Synchronous Parallel Implementation of Push-Relabel
3.1 Improving the Algorithm
4 Evaluation
4.1 A Modern Benchmark Suite for Flow Computations
4.2 Comparison and Testing Methodology
4.3 Results
5 Conclusion
Towards Tight Lower Bounds for Scheduling Problems
1 Introduction
2 Preliminaries
3 Structured k-partite Problem
4 Lower Bounds for Scheduling Problems
Q|prec |Cmax
P|prec, pmtn, pj=1 |Cmax
5 Discussion
1-Planar Graphs have Constant Book Thickness
1 Introduction
2 Definitions and Yannakakis' Algorithm
3 An Upper Bound on the Page Number of 1-Planar Graphs
3.1 The Two-Level Case
3.2 The Multi-Level Case
4 Conclusions and Open Problems
Access, Rank, and Select in Grammar-compressed Strings
1 Introduction
2 Notation and Preliminaries
3 Improved Access Time with Rank and Select Support
3.1 The Method of Bille et al .
3.2 Heavy Path Decomposition of a DAG
3.3 Biased Skip Trees
3.4 Improved Access Time
4 Optimal Access Time for Not-so-compressible Strings
4.1 Fast Queries for Unbalanced Grammars
5 Hardness of Rank/Select in Grammar-compressed Strings
6 Concluding Remarks
Fully-Dynamic Approximation of Betweenness Centrality
1 Introduction
2 Related Work
2.1 Overview of Algorithms for Computing BC
2.2 RK Algorithm
2.3 IA and IAW Algorithms
2.4 Batch Dynamic SSSP Algorithms
3 New VD Approximation for Weighted Graphs
4 New Fully-Dynamic Algorithms
5 Experiments
6 Conclusions
Improved Purely Additive Fault-Tolerant Spanners
1 Introduction
1.1 Our Results
1.2 Related Work
1.3 Notation
2 Augmenting Sourcewise Fault-Tolerant Spanners
3 Augmenting Clustering-Based Additive Spanners
Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
1 Introduction
2 Preliminaries
3 Path and Tree Decompositions with Few Bags
3.1 Finding Path Decompositions with Memorizationand Isomorphism Tests
3.2 The Number of Good Pairs
3.3 Analysis of the Algorithm
3.4 Extension to Finding Tree Decompositions
4 Lower Bound
Enumeration of 2-Level Polytopes
1 Introduction
1.1 Contribution and Outline
1.2 Previous Work
2 Preliminaries
3 Embeddings
3.1 Slack Matrices and Slack Embeddings
3.2 Simplicial Cores
3.3 H- and V-Embeddings
4 Algorithm
4.1 Closed Sets
4.2 The Enumeration Algorithm
4.3 Implementation
5 Experimental Results
5.1 Outcome of the Experiments
6 Discussion
Upper and Lower Bounds for Online Routingon Delaunay Triangulations
1 Introduction
2 A Generalization of Chew's Routing Algorithm
3 Routing Ratio
3.1 Preliminaries
3.2 Proof of Theorem 1
3.3 Proof of the Key Lemma
4 Lower Bounds
On Computing the Hyperbolicityof Real-World Graphs
1 Introduction
2 CCL: The Currently Best Available Algorithm
3 HYP: The New Algorithm
4 Experimental Results
5 Synthetic Graphs
6 Conclusion and Open Problems
Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs
1 Introduction
2 Structural Properties
3 Algorithmic Toolbox
3.1 An nO(k) Time Algorithm
4 A Fully Polynomial Time Algorithm
4.1 Dynamic Programming Tree
4.2 Dynamic Programming Table
4.3 Non-base Case of the Dynamic Program
Consensus Patterns (Probably) Has no EPTAS
1 Introduction
1.1 Methods
2 Hardness of Approximating Colored Consensus String with Outliers
3 Hardness of Approximating Consensus Patterns
4 Conclusions and Future Work
Fast Quasi-Threshold Editing
1 Introduction
1.1 Our Contribution
1.2 Outline
1.3 Preliminaries
2 Lower Bounds
3 Linear Recognition and Initial Editing
4 The Quasi-Threshold Mover Algorithm
5 Experimental Evaluation
6 Conclusion
Sublinear Estimation of Weighted Matchingsin Dynamic Data Streams
1 Introduction
1.1 Preliminaries
2 Weighted Matching
2.1 Applications
3 Lower Bound
An Improved Approximation Algorithmfor Knapsack Median Using Sparsification
1 Introduction
1.1 Preliminaries
2 An Improved Approximation Algorithm for Knapsack Median
2.1 Kumar's Bound
2.2 Sparse Instances
2.3 Improving Kumar's Bound and Modifying the LP Relaxation
2.4 Filtering Phase
2.5 A Basic (23.09+)-Approximation Algorithm
2.6 A (17.46+)-Approximation Algorithm via Conditioning on the Fractional Cluster Center
3 A Bi-Factor 3.05-Approximation Algorithm for Knapsack Median
3.1 Pruning the Instance
3.2 Computing and Rounding a Bi-Point Solution
4 Discussion
Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
1 Introduction
2 Theoretical Preliminaries
3 Dual Variant of Benson's Algorithm
4 Lexicographic Dual Benson
5 Computational Study
Self-Adjusting Binary Search Trees: What Makes Them Tick?
1 Introduction
2 Disjoint and Monotone Sets
3 Zigzag Sets
4 New Heuristics: Depth Reduction
5 Necessary Conditions
5.1 Necessity of O(1) Monotone Sets
5.2 Necessity of Many Leaves
6 Small Monotonicity-Depth and Local Algorithms
On Element-Connectivity Preserving Graph Simplification
1 Introduction
2 Preliminaries
3 Element-Connectivity and Connections to Submodularity
4 Algorithmic Aspects of Element-Connectivity
Computing Element-Connectivity
Computing a Reduced Graph
5 Proof of Reduction Lemma via Setpairs
On Randomized Algorithms for Matching in the Online Preemptive Model
1 Introduction
2 Barely Random Algorithms for MCM
2.1 Randomized Algorithm for MCM on Growing Trees
3 Lower Bounds
3.1 Lower Bound for MWM
3.2 Lower Bound for Structured Graphs
4 Randomized Algorithm for Paths
A Characterization of Consistent Digital Line Segments in Z2
1 Introduction
2 Preliminaries
3 A Characterization of CDSes in Z2
4 Luby and Christ et al. in the Context of Our Characterization
On the Efficiency of All-Pay Mechanisms
1 Introduction
1.1 Contribution
1.2 Related Work
2 Preliminaries
3 Combinatorial Auctions
3.1 Proof of Inequality (1)
3.2 Proof of Inequality (2)
3.3 Proof of Inequality (4)
4 Multi-unit Auctions
5 Single Item Auctions
Dictionary Matching in a Stream
1 Introduction
1.1 Related Work
1.2 Definitions
2 Short Patterns
3 Long Patterns
3.1 Algorithm A2a: Patterns with Short Periods
3.2 Algorithm A2b: Patterns with Long Periods
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
1 Introduction
2 Preliminaries
3 The Cross-Metric Setting
4 Structural Properties of a Shortest Multicut Dual
4.1 Crossing Bound
4.2 Some Shortest Multicut Dual is Good
5 Enumerating Topologies
6 Dealing With Each Valid Topology
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
1 Introduction
2 Preliminaries
3 Structure Theorem
4 Algorithm
5 Computing Cut Graphs for Bounded Tree-Width
5.1 A Simpler Version of Surface-Cut Decompositions
5.2 Making a Graph Polyhedral
5.3 Dynamic Programming on Surface-Cut Decompositions
Explicit Expanding Expanders
1 Introduction
1.1 Our Results and Techniques
1.2 Related Work
2 Preliminaries: Expander Graphs and Expansion Cost
3 Construction and Some Observations
4 Analysis: Expansion and Expansion Cost
4.1 Edge Expansion
5 Improved Edge Expansion Analysis
6 Open Questions
On the Threshold of Intractability ,
1 Introduction
2 Preliminaries
3 Hardness
4 Quadratic Kernels for Threshold and Chain Editing
5 Subexponential Time Algorithms
6 Conclusion
A Polynomial Kernel for Trivially Perfect Editing
1 Introduction
2 Kernel for Trivially Perfect Editing:Proof of Theorem 1
3 Conclusions
Polymatroid Prophet Inequalities
1 Introduction
2 Preliminaries
3 Algorithm for Polymatroids
3.1 Block-Structured Matroids
3.2 Prophet Inequality for Block-Structured Matroids
3.3 Prophet Inequality for Polymatroids
3.4 Proof of the Block-Restricted Matroid Prophet Inequality
4 Application to Mechanism Design
Node-Balancing by Edge-Increments
1 Introduction
2 A Characterization of Equatable Graphs
3 A Polynomial-Time Algorithm to Equate the Weights
4 Bipartite Graphs
4.1 Hypergraphs
The Price of Matching with Metric Preferences
1 Introduction
1.1 Related Work
2 Setting and Preliminaries
3 Price of Anarchy
4 Price of Stability
4.1 An Algorithm for -Stable Matchings
4.2 Cost Analysis
Selfish Vector Packing
1 Introduction
2 Price of Anarchy
2.1 Upper Bound
2.2 Lower Bound
2.3 Other Variants
3 Strong Price of Anarchy
Approximate Deadline-Schedulingwith Precedence Constraints
1 Introduction
1.1 Deadline Scheduling and Technology Diffusion
2 Notation
3 An Integer Programming Formulation
4 Rounding the Relaxation
5 Solving LP (P)
Prophet Secretary
1 Introduction
2 Our Contributions
3 Preliminaries
3.1 Two Thresholds Breaks 12 Barrier
4 (1-1e0.63)-Competitive Ratio Using n Thresholds
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
1 Introduction
1.1 Related Work
2 Outline of Our Analysis
3 Preliminaries and Notation
4 Improvement of a Double Movement
5 Phase 1
6 Phase 2
7 Bounding the Expected Number of Steps
8 Concluding Remarks
Maximizing Symmetric Submodular Functions
1 Introduction
1.1 Our Techniques
1.2 Related Work
2 Preliminaries
3 Measured Continuous Greedy for Symmetric Functions
4 Equality Cardinality Constraints
Approximating LZ77 viaSmall-Space Multiple-Pattern Matching
1 Introduction
2 Preliminaries
2.1 Fingerprints
2.2 Tries
3 Short Patterns
4 Long Patterns
4.1 Patterns without Long Highly Periodic Prefix
4.2 Highly Periodic Patterns
4.3 Summary
5 Approximating LZ77 in Small Space
5.1 2-Approximation Algorithm
5.2 Approximation Scheme
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
1 Introduction
2 Preliminaries
3 Multiset Separators and Representative Sets
4 Algorithmic Applications
5 Low Degree Monomials and Low DegreeSpanning Trees
6 Conclusions
Medial Axis Based Routing Has Constant Load Balancing Factor
1 Introduction
2 Network Model and Medial Axis
3 Our Medial Axis Based Routing Scheme
3.1 Step 2: The Flow Program
3.2 Step 3: Compact Representation of
3.3 Extending to on
4 Proof of Approximation Guarantee
5 Discussions and Open Problems
An Experimental Evaluationof the Best-of-Many Christofides' Algorithmfor the Traveling Salesman Problem
1 Introduction
2 Algorithms
2.1 Column Generation
2.2 Splitting Off and Tree Packing
2.3 SwapRound and Negatively Correlated Distributions
2.4 The Maximum Entropy Distribution
3 Experiments
4 Results
5 Conclusions
Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
1 Introduction
2 Preliminaries
3 Approximation Algorithms and Heuristics
3.1 Independent Spanning Trees
4 Experimental Analysis
A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations
1 Introduction
2 Delaunay and Witness Complexes
3 Identity of Witness and Delaunay Complexes
4 Turning Witness Complexes into Delaunay Complexes
4.1 Lovász Local Lemma
4.2 Correctness of the Algorithm
5 Sublinear Algorithm
5.1 The Relaxed Delaunay Complex
5.2 Computing Relaxed Delaunay Centers
5.3 Construction of Del20(L',W)
5.4 Correctness of the Algorithm
A Characterization of Visibility Graphs for Pseudo-polygons
1 Introduction
2 Preliminaries
3 Necessary Conditions
4 Proving the Conditions Are Sufficient
Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search
1 Introduction
2 Excesses IBFS
3 Improvements to IBFS and Excesses IBFS
4 Experimental Results
The Temp Secretary Problem
1 Introduction
2 Formal Statement of Problems Considered
3 The Time-Slice Algorithm
4 Improved Results for the Temp Secretary Problemfor the Uniform Arrival Distribution
4.1 The Temp Secretary Algorithm, Ck,: A Competitive Ratio of 1/(1+k)
4.2 Outline of the Proof of Theorem 2
5 Upper Bound for the Temp Secretary Problem with Uniform Arrival Times and with No Budget Restriction
6 About Theorem 3: A Lower Bound on the Expected Size of the Maximum -independent Subset
7 Discussion and Open Problems
How to Sort by Walking on a Tree
1 Introduction
2 Notation and General Bounds
3 Sorting on Paths
4 Sorting on Trees
4.1 Cycle Anchor Trees
4.2 Reconstructing a Sorting Walk
4.3 Finding a Cheapest Cycle Anchor Tree
5 Sorting on Other Graphs
6 Conclusion
Improved Analysis of Complete-Linkage Clustering
1 Introduction
1.1 Problem Definitions and Algorithms
1.2 Related Work
1.3 Our Results
2 Clustering Intersection Graphs
2.1 Definition and Fundamental Properties
2.2 The One-Dimensional Case
2.3 Completion of the CI-Graph
2.3 Analysis of H at Different Time Steps
3 Approximation Factor of `3´9`42`"?613A``45`47`"603ACL in the Case d2
3.1 CI-Graphs with at most 2k Vertices
3.2 Approximation Factor of CL
4 Conclusions
Structural Parameterizations of the Mixed Chinese Postman Problem
1 Introduction
2 Properly Balanced Subgraph Problem
2.1 Gadgets for PBS
2.2 W[1]-Hardness of PBS
3 Reducing PBS to MCPP
4 PBS Parameterized by Treedepth
4.1 Fixed-Parameter Tractability of PBS
5 Positive Result: Reducing MCPP to PBS
6 Discussion
Online Appointment Scheduling in the Random Order Model
1 Introduction
1.1 Related Work
2 Jobs with Uniform Processing Time
2.1 Bound on Tentative Slot Numbers
2.2 From Tentative to Actual Slots
2.3 Putting the Pieces Together
3 General Jobs
4 Lower Bound for Fully Worst-Case Input
Approximation Algorithms for Connected Maximum Cut and Related Problems
1 Introduction
1.1 Related Work
1.2 Contribution and Techniques
2 Approximation Algorithms for General Graphs
2.1 Obtaining an (1logn) Approximation
3 CMC in Planar and Bounded Genus Graphs
3.1 PTAS for Bounded Genus Graphs
3.2 NP-Hardness in Planar Graphs
The Offset Filtration of Convex Objects
1 Introduction
2 Topological Background
3 Barcodes of Restricted Offsets
4 Barcodes of Restricted Offsets in 2D
5 Barcodes of Restricted Offsets in 3D
6 Polygons vs. Point Samples: Experimental Comparison
Approximation Algorithmsfor Polynomial-Expansion and Low-Density Graphs
1 Introduction
2 Preliminaries
2.1 Low-Density Graphs
2.2 Graphs with Polynomial Expansion
3 Approximation Algorithms
4 Hardness of Approximation
Monotone Drawings of 3-Connected Plane Graphs
1 Introduction
2 Preliminaries
3 Schnyder Drawing of 3-Connected Plane Graphs is Monotone
4 Conclusion
Faster Fully-Dynamic Minimum Spanning Forest
1 Introduction
1.1 Related Work
1.2 Idea and Paper Outline
2 Reduction to Decremental MSF
3 Simple Data Structures for Dynamic Connectivityand Decremental MSF
3.1 Handling Insertions and Deletions
3.2 Local Trees
3.3 Supporting Decremental MSF
4 Faster Data Structure for Dynamic MSF
4.1 A Downwards Shortcutting System
4.2 Dealing with Non-Topological Changes
4.3 Dealing with Topological Changes
On the Equivalence among Problems of Bounded Width
1 Introduction
1.1 Overview of Decomposition-Based Reductions
1.2 Organization
2 Preliminaries
3 Tree-width Preserving Reduction from Max 2-SAT to SAT
4 Exactly Parameterized NL
Fast Output-Sensitive Matrix Multiplication
1 Introduction
1.1 Preliminaries
1.2 Our Results
1.3 Related Work
2 The Row Balanced Case
3 Subdividing into Balanced Parts
4 The Balanced Case
4.1 A Data Structure for Balanced Output
4.2 Creating the Output as Sparse Matrix
A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
1 Introduction
2 Preliminaries
3 ILPs of Bounded Treewidth
3.1 Tree Decompositions of Linear Programs
3.2 Feasibility on Gaifman Graphs of Bounded Treewidth
3.3 Protrusion Reductions
3.4 Limitations for Replacing Protrusions
4 Totally Unimodular Subproblems
5 Discussion and Future Work
On the Approximability of Digraph Ordering
1 Introduction
1.1 Related Work
1.2 Our Results
1.3 Overview of Techniques
2 Preliminaries
2.1 LP Relaxation for Max-k-Ordering
3 A 2-Approximation for Max-k-Ordering
4 Approximation for OffsetRMAS
Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems
1 Introduction
2 Preliminaries
3 Radio Spectrum Reallocation
3.1 Main Results
3.2 Proof of Theorem 1 (Approximation)
4 Network Bandwidth Reallocation
5 Cost Minimization with Set Cover Constraints
On the Pathwidth of Almost Semicomplete Digraphs
1 Introduction
2 Notation
3 Algorithm
4 Tame Obstacles Survive Random Sampling:Proof Sketch of Theorem 2
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence
1 Introduction
2 Relation to Previous Work
3 Our Results
4 Preliminaries
5 Min-Wise Hashing
5.1 Upper Bounds
5.2 Lower Bounds
6 Quicksort
6.1 Binary Planar Partitions and Randomized Treaps
7 Largest Bucket Size
7.1 Upper Bound
7.2 Lower Bound
Maximum Matching in Turnstile Streams
1 Introduction
2 Preliminaries
3 Hard Input Distribution
3.1 Hard Input Distribution: Global View
3.2 Hard Input Distribution: Local View
4 Simultaneous Message Complexity Lower Bound
5 Upper Bound
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
1 Introduction
2 The Lasserre Hierarchy
3 Partial Diagonalization
4 A Lower Bound for Min-Number of Tardy Jobs
4.1 The Starting Linear Program
4.2 The Integrality Gap Instance
4.3 Proof of Integrality Gap for Last(LP(T))
5 Application in 0/1 Polynomial Optimization
Optimal Parameterized Algorithmsfor Planar Facility Location ProblemsUsing Voronoi Diagrams
1 Introduction
2 Geometric Problems
3 The General Problem
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
1 Introduction
2 Problem Definition, Notation and Structural Insights
3 A Randomized Algorithm for MST under Uncertainty
4 Non-uniform Query Cost
4.1 Balancing Algorithm
4.2 Randomization for Non-uniform Query Cost
5 Computing the MST Weight under Uncertainty
6 Matroids under Uncertainty
Compressed Data Structuresfor Dynamic Sequences
1 Introduction
2 O(nlogn)-Bit Data Structure
3 O(nlog)-Bit Data Structure
4 Compressed Data Structure
4.1 Compressed Data Structure for & n/log3 n
5 Compressed Data Structure II
6 Substring Extraction
A.1 Prefix Sum Queries on a List
Geometric Hitting Sets for Disks: Theory and Practice
1 Introduction
2 A Near Linear Time Algorithm for Computing -nets for Disks in the Plane
3 Engineering the Agarwal-Pan Algorithm
4 Implementation and Experimental Evaluation
Efficient Computation of Middle Levels Gray Codes
1 Introduction
2 The Algorithm
2.1 Basic Definitions
2.2 Computing Paths in Q2n(n,n+1)
2.3 Computing a Hamilton Cycle in the Middle Levels Graph
2.4 The Top-Level Algorithm
2.5 Flip Vertex Computation
3 Runtime Analysis
Computing the SimilarityBetween Moving Curves
1 Introduction
1.1 Results
2 Synchronous Dynamic Matchings
2.1 Freespace Partitions in 2D
2.2 Freespace Partitions in 3D
2.3 Parametric Search
2.4 A Faster Decision Algorithm
3 Hardness
I/O-Efficient Similarity Join
1 Introduction
2 Related Work
3 Our Algorithms
3.1 Cache-Aware Algorithm: ASimJoin
3.2 Cache-Oblivious Algorithm: OSimJoin
3.3 I/O Complexity and Correctness of OSimJoin
3.4 Removing Duplicates
4 Conclusion
Improved Approximation Algorithms for Weighted 2-Path Partitions
1 Introduction
2 M2PP in General Graphs
2.1 The WeightedDoubleMatching Algorithm
3 M2PP on {0, 1}-Edge-Weighted Graphs
4 MTP on {0, 1}-Edge-Weighted Graphs
5 Conclusions
A Multivariate Approach for Weighted FPT Algorithms
1 Introduction
1.1 Previous Work
1.2 Our Results
2 Preliminaries
3 A General Multivariate Approach
4 An O*(1.381s) Time Algorithm for WVC
Incidences with Curves in Rd
1 Introduction
2 The Three-Dimensional Case
3 Incidences in Higher Dimensions
D3-Tree: A Dynamic Deterministic Decentralized Structure
1 Introduction
2 The D3-Tree
2.1 The Structure
2.2 Node Joins and Departures
2.3 Single and Range Queries
2.4 Element Insertions and Deletions
2.5 Fault Tolerance
2.6 Single Queries with Node Failures
3 Experimental Study
4 Conclusions
Ignorant vs. Anonymous Recommendations
1 Introduction
2 Related Work
3 Model
4 Anonymous Recommendations
4.1 Consistency Graph
5 Learning the Preferences
5.1 Finding a 1-Entry
5.2 Progress
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Highway Dimension
2.2 Definition of Gt,k,q
2.3 Properties of Gt,k,q
3 Hub Labeling
3.1 The Algorithm
3.2 Lower Bounding the Query Time
3.3 Hardness of Preprocessing
4 Contraction Hierarchies
4.1 The Algorithm
4.2 Lower Bounding the Query Time
4.3 Lower Bounding the Size of E+
5 Transit Node Routing
5.1 Lower Bounding the Query Time
6 Conclusions and Future Work
Trip-Based Public Transit Routing
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Related Work
3 Algorithm
3.1 Preprocessing
3.2 Earliest Arrival Query
3.3 Profile Query
3.4 Implementation
3.5 Journey Descriptions
4 Experiments
5 Conclusion
Mixing Color Coding-Related Techniques
1 Introduction
2 Color Coding-Related Techniques
3 Our Mixing Strategies
3.1 Strategies I and II
3.2 Strategy III
3.3 Strategy IV
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Algorithms - ESA 2015

Description

More details

Other editions

Additional editions

Content

System requirements