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

Front Matter....Pages I-XXIII
Improved Approximation Algorithms for Stochastic Matching....Pages 1-12
Sorting and Permuting without Bank Conflicts on GPUs....Pages 13-24
Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons....Pages 25-34
Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems....Pages 35-46
Buffer Management for Packets with Processing Times....Pages 47-58
A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem....Pages 59-70
Exact Minkowski Sums of Polygons With Holes....Pages 71-82
Revenue Maximization for Selling Multiple Correlated Items....Pages 83-94
Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm....Pages 95-105
Towards Tight Lower Bounds for Scheduling Problems....Pages 106-117
1-Planar Graphs have Constant Book Thickness....Pages 118-129
Access, Rank, and Select in Grammar-compressed Strings....Pages 130-141
Fully-Dynamic Approximation of Betweenness Centrality....Pages 142-154
Improved Purely Additive Fault-Tolerant Spanners....Pages 155-166
Subexponential Time Algorithms for Finding Small Tree and Path Decompositions....Pages 167-178
Enumeration of 2-Level Polytopes....Pages 179-190
Upper and Lower Bounds for Online Routing on Delaunay Triangulations....Pages 191-202
On Computing the Hyperbolicity of Real-World Graphs....Pages 203-214
Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs....Pages 215-226
Consensus Patterns (Probably) Has no EPTAS....Pages 227-238
Fast Quasi-Threshold Editing....Pages 239-250
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams....Pages 251-262
An Improved Approximation Algorithm for Knapsack Median Using Sparsification....Pages 263-274
Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems....Pages 275-287
Self-Adjusting Binary Search Trees: What Makes Them Tick?....Pages 288-299
On Element-Connectivity Preserving Graph Simplification....Pages 300-312
On Randomized Algorithms for Matching in the Online Preemptive Model....Pages 313-324
On the Efficiency of All-Pay Mechanisms....Pages 325-336
Dictionary Matching in a Stream....Pages 337-348
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals....Pages 349-360
A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface....Pages 361-372
Explicit Expanding Expanders....Pages 373-385
On the Threshold of Intractability....Pages 386-398
A Polynomial Kernel for Trivially Perfect Editing....Pages 399-410
Polymatroid Prophet Inequalities....Pages 411-423
Node-Balancing by Edge-Increments....Pages 424-436
The Price of Matching with Metric Preferences....Pages 437-449
Selfish Vector Packing....Pages 450-458
Approximate Deadline-Scheduling with Precedence Constraints....Pages 459-470
Prophet Secretary....Pages 471-482
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem....Pages 483-495
Maximizing Symmetric Submodular Functions....Pages 496-508
Approximating LZ77 via Small-Space Multiple-Pattern Matching....Pages 509-520
Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints....Pages 521-532
Medial Axis Based Routing Has Constant Load Balancing Factor....Pages 533-544
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem....Pages 545-556
Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs....Pages 557-569
A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations....Pages 570-581
A Characterization of Visibility Graphs for Pseudo-polygons....Pages 582-594
Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search....Pages 595-606
The Temp Secretary Problem....Pages 607-618
How to Sort by Walking on a Tree....Pages 619-630
Improved Analysis of Complete-Linkage Clustering....Pages 631-642
Structural Parameterizations of the Mixed Chinese Postman Problem....Pages 643-655
Online Appointment Scheduling in the Random Order Model....Pages 656-667
Approximation Algorithms for Connected Maximum Cut and Related Problems....Pages 668-679
The Offset Filtration of Convex Objects....Pages 680-692
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs....Pages 693-704
Monotone Drawings of 3-Connected Plane Graphs....Pages 705-716
Faster Fully-Dynamic Minimum Spanning Forest....Pages 717-728
On the Equivalence among Problems of Bounded Width....Pages 729-741
Fast Output-Sensitive Matrix Multiplication....Pages 742-753
A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity....Pages 754-765
On the Approximability of Digraph Ordering....Pages 766-778
Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems....Pages 779-791
On the Pathwidth of Almost Semicomplete Digraphs....Pages 792-803
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence....Pages 804-815
Maximum Matching in Turnstile Streams....Pages 816-827
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem....Pages 828-839
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams....Pages 840-852
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty....Pages 853-864
Compressed Data Structures for Dynamic Sequences....Pages 865-877
Geometric Hitting Sets for Disks: Theory and Practice....Pages 878-890
Efficient Computation of Middle Levels Gray Codes....Pages 891-902
Computing the Similarity Between Moving Curves....Pages 903-914
I/O-Efficient Similarity Join....Pages 915-927
Improved Approximation Algorithms for Weighted 2-Path Partitions....Pages 928-940
A Multivariate Approach for Weighted FPT Algorithms....Pages 941-952
Ignorant vs. Anonymous Recommendations....Pages 953-964
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms....Pages 965-976
Trip-Based Public Transit Routing....Pages 977-988
Mixing Color Coding-Related Techniques....Pages 989-1000
Back Matter....Pages 1001-1012
....Pages 1013-1024