Algorithms and Data Structures

Name: Algorithms and Data Structures | 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011, Proceedings

Frank Dehne John Iacono Jörg-Rüdiger Sack(Herausgeber*in)

Springer (Verlag)

Erschienen am 18. Juli 2011

XV, 718 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22300-6 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Piecewise-Linear Approximations of Uncertain Functions
Introduction
The min-$k$ Problem
The min-e Problem
References
A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs
Introduction
Preliminaries
Notations
A Vertex Numbering Scheme for Circular Arc Graphs
Computing the Boxicity of Co-bipartite CA Graphs in Polynomial Time
Reducing the Time Complexity of Computing the Boxicity of Co-bipartite CA Graphs
Constant Factor Approximation for the Boxicity of CA Graphs
Additive 2-Factor Approximation for the Boxicity of Normal CA Graphs
References
On the Area Requirements of Euclidean Minimum Spanning Trees
Introduction
Preliminaries
Geometric Lemmata
Angles and Edge Lengths in MST Embeddings
The Proof of the Area Bound
Conclusions
References
Multi-target Ray Searching Problems
Introduction
Ray Search in the Full-Information Model
Ray-Search in the Partial-Information Model
Intrinsic Cost of Multi-target Search
A $O(logm)$-Competitive Algorithm
An Asymptotically Optimal Multi-target Search Algorithm
Conclusions
References
Convex Transversals
Introduction
Hardness Results
Stabbing Segments in the Plane is NP-Hard
Extensions
Stabbing Disjoint Segments and Convex Pseudodisks
Convexification
Stabbing with Vertices of a Regular Polygon
Polynomial-Time Algorithm
Optimization Problem: Symmetry with Imprecision
References
How to Cover a Point Set with a V-Shape of Minimum Width
Introduction
Reduction to Canonical V-Shapes
Computing a Canonical Minimum-Width V-Shape
A 13-Approximation Algorithm
Minimum-Width V-Shape for Points on Two Lines
A (1 + e)-Approximation Algorithm
Concluding Remarks
References
Witness Rectangle Graphs
Introduction
Structure of Witness Rectangle Graphs
Two Connected Components
What Are Staircase Graphs, Really?
How to Stab Rectangles, Thriftily
References
Faster Optimal Algorithms for Segment Minimization with Small Maximal Value
Introduction
Single-Row Segmentation
Full-Matrix Segmentation
Segmenting a Row under Constraints
Full-Matrix
Further Improvements of the Complexity
Solving the Lex-Min Problem
The Special Case of $H = 2$
Single Row for $H = 2$
Full Matrix Segmentation for $H = 2$
Conclusion
References
Orthogonal Cartograms with Few Corners Per Face
Introduction
Background and Preliminaries
Dart-Shaped Graphs
Algorithm for Orthogonal Cartograms
T-Staircases
Decomposing T-Staircases
Pinning Dart-Shaped Graphs to T-Staircases
Remarks
References
Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
Introduction
Preliminaries
Euclidean Functionals
Smoothed Analysis
Framework
Smoothed Running-Time
Smoothed Approximation Ratio
Matching
Smoothed Running-Time
Smoothed Approximation Ratio
Karp's Partitioning Scheme for Euclidean TSP
Euclidean Steiner Trees
Degree-Bounded Minimum Spanning Tree
Concluding Remarks
References
Feedback Vertex Set in Mixed Graphs
Introduction
Preliminaries
Outline of the Algorithm
An Algorithm for FVS/UMC: Reduction to Skew Separator
An Algorithm for S-Disjoint FVS: Contracting Paths
Discussion
References
Switching to Directional Antennas with Constant Increase in Radius and Hop Distance
Introduction
a = p/3
a = p/3
PointsalongaPath
References
Frequency Capping in Online Advertising (Extended Abstract)
Introduction
Related Work
Preliminaries
Identical Valuations
Equal Demand Case
General Case
Equal Demands/Arbitrary Valuations
Arbitrary Valuations
A Primal-Dual Algorithm
Further Directions
References
Adjacency-Preserving Spatial Treemaps
Introduction
Preliminaries
Preserving Orientations
Given the Global Layout
Unconstrained Global Layout
Without Preserving Orientations
References
Register Loading via Linear Programming
Introduction
Reduction
1-BSIM
LP Rounding
$k$-BSIM
Conclusion
References
Connecting a Set of Circles with Minimum Sum of Radii
Introduction
CRA for a Given Connectivity Tree
Range Assignment for Bounded Radii
Solutions with a Bounded Number of Circles
Polynomial-Time Approximation Schemes
Unbounded Radii
Bounded Radii
Experimental Results
Conclusion
References
Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions
Introduction
Streaming MEB
Preliminaries and Agarwal and Sharathkumar's Algorithm
An Improved Analysis
Proof of Factor 4/3
Proof of Factor 16/13
Proof of Factor 1.22
Dynamic MEB
Preliminaries and a Dynamic Coreset Technique
A New Dynamic Algorithm
Final Remarks
References
New Algorithms for 1-D Facility Location and Path Equipartition Problems
Introduction
Related Work
The Problem Modeling of the Facility Location
The $k$-Median Problem
The Infinity $k$-Coverage Problem
The Linear Model
The Path Equipartition Problems
References
Multicut in Trees Viewed through the Eyes of Vertex Cover
Introduction
Preliminaries
The Kernel
The Algorithm
References
Beyond Triangulation: Covering Polygons with Triangles
Introduction
NP-Hardness of the Triangle Cover Problem
Inapproximability
Covering without Steiner Points
Covering the Boundary
References
Lossless Fault-Tolerant Data Structures with Additive Overhead
Introduction
Fundamental Techniques
Blocked Fault-Tolerant Data Structures
Fault-Resistant Operations
Fault-Tolerant Operations
Fault-Tolerant Memory
Fault-Tolerant Predecessor
Suffix Trees
Fault-Resistant Tries
Fault-Tolerant Suffix Trees
Interval Trees
References
Binary Identification Problems for Weighted Trees
Introduction
Proofs of Strong NP-Hardness
A Polynomial Time Algorithm for Diameter 5 Instances
A Quadratic Time Algorithm for Path Instances
An $o(logn)$ Approximation Algorithm
References
Computing the Fr´echet Distance between Folded Polygons
Introduction
Preliminaries
Simple Polygons Algorithm Summary
Shortest Path Edge Sequences
Diagonal Monotonicity Test and Untangleability
Fixed-Parameter Tractable Algorithm
Untangleability Space
Fixed-Parameter Tractable Algorithm
Constant Factor Approximation Algorithm
Axis-Parallel Folds and $L8$ Distance
Future Work
References
Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
Introduction
Some Equivalent Parameterized Graph Editing Problems
Solving Star Editing Faster than 3-Hitting Set
Open Questions
References
Path Minima Queries in Dynamic Weighted Trees
Introduction
Previous Work
Our Results
Preliminaries
Data Structures for Dynamic Weights
Comparison-Based Data Structure
RAM Structure
Data Structures for Dynamic Leaves
Optimal Semigroup Structure
RAM Structure
Lower Bounds
References
On Rectilinear Partitions with Minimum Stabbing Number
Introduction
Finding Optimal Rectilinear r-Partitions Is NP-Hard
Polynomial Time Algorithms for Constant r
Arbitrary versus Disjoint Rectilinear r-Partitions
Experimental Results
Results of the Comparisons
Conclusion
References
Flattening Fixed-Angle Chains Is Strongly NP-Hard
Introduction
Definitions
Linkages
Rectilinear Planar Monotone 3-SAT
Flattening Semi-rigid Chains
Flattening Fixed-Angle Chains and Trees
Flat Span
References
An $O(n log n)$ Algorithm for a Load Balancing Problem on Paths
Introduction
Preliminaries
Hydraulic Apparatus
An $O(n log n )$ Algorithm
Conclusion and Open Problems
References
Fully-Dynamic Hierarchical Graph Clustering Using Cut Trees
Introduction
Preliminaries and Notation
The Static Hierarchical Clustering Algorithm
Update Algorithm for Dynamic Clustering Hierarchies
Conclusion
References
Flow Computations on Imprecise Terrains
Introduction
NP-Hardness in the Surface Model
Watersheds in the Network Model
Potential Watersheds
Core Watersheds
Persistent Watersheds - An Alternative Definition
Potential Downstream Areas
Conclusions
References
Tracking Moving Objects with Few Handovers
Introduction
Problem Statement and Notation
Offline Tracking
Online Tracking
Lower Bounds
Trilateration
Conclusions
References
Inducing the LCP-Array
Introduction
Previous Work and Concepts
Suffix- and LCP-Arrays
Constructing Suffix Arrays by Induced Sorting
Inducing the LCP-Array
Basic Algorithm
Finding Minima
Computing LCP-Values of S*-Suffixes
Computing LCP-Values at the L/S-Seam
Experimental Results
Conclusions and Outlook
References
Horoball Hulls and Extents in Positive Definite Space
Introduction
Hulls and Convexity: From $R^d to P(n)$
Technical Overview
Related Work
Preliminaries
Busemann Functions and Horoballs
Ball Hulls
The e -Ball Hull
Constructing the e -Ball Hull
Decomposing P($n$) into Flats
A Lipschitz Bound in P(2)
Generalizing to P($n$)
Algorithm
References
Enumerating Minimal Subset Feedback Vertex Sets
Introduction
Preliminaries
Enumeration of All Minimal Subset Feedback Vertex Sets
Running Time
Concluding Remarks
References
Upper Bounds for Maximally Greedy Binary Search Trees
Introduction
A Geometric View
Being Greedy
Our Contributions
A Note on Independent Work
Arboral and Geometric Models of BSTs
The Arboral Model
The Geometric Model
GreedyFuture
An Access Lemma and Its Corollaries
Potentials and Neighborhoods
Immediate Consequences
Telescoping Rank Changes
Counting Stubborn Elements
Finishing the Proof
A Sequential Access Theorem
Closing Remarks
References
On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations
Introduction
Technical Development
Outline
Existence of the Permutation
Linear Off-Line Implementation
Some Remarks
References
Resilient and Low Stretch Routing through Embedding into Tree Metrics
Introduction
Preliminaries
Constant Distortion Routing Using Two HSTs
Resilience to Node Failures Using Two HSTs
Simulations
References
Consistent Labeling of Rotating Maps
Introduction
Model
Properties of Consistent Labelings
Complexity
Basic Building Blocks
Gadgets of the Reduction
Approximation Algorithms
A 1/4-Approximation for MaxTotal
An Efficient Polynomial-Time Approximation Scheme for MaxTotal
References
Finding Longest Approximate Periodic Patterns
Introduction and Related Work
Optimal Algorithm for Absolute Error Periodic Patterns
Algorithms for Relative Error Periodic Patterns
An Exact Algorithm
A Basic Approximate Algorithm
An Approximate $O(n1+?)$Time Algorithm
Solving Approximate 3SUM in $O(n1+?+Tsort(n))$ Time
References
A (5/3 + e)-Approximation for Strip Packing
Introduction
Overview of the Algorithm
Item of Height Greater than 1/3
One Special Big Item in $P$
Overview of the Cases
References
Reversing Longest Previous Factor Tables is Hard
Introduction
Preliminaries
Notations and Definitions
Simple Properties of LPF Tables
Reduction from 3-SAT
Variable Section
Assignment Section
Checking Section
LPF Tables with 0-1 Entries
References
Space Efficient Data Structures for Dynamic Orthogonal Range Counting
Introduction
Our Results
Data Structures for Range Sum
Range Sum in a Small Two-Dimensional Array
Range Sum in a Narrow Two-Dimensional Array
Range Counting in Integer Sequences
Sequences of Small Integers
General Integer Sequences
Range Counting in Planar Point Sets
Range Counting on a U × U Grid
Range Counting for General Point Sets
Concluding Remarks
References
Searching in Dynamic Tree-Like Partial Orders
Introduction
Models and Definitions
Line-Leaf Tree Construction and Analysis
Operations
Empirical Results
References
Counting Plane Graphs: Flippability and Its Applications
Introduction
Applications of Ps-Flippable Edges
The Ratio between the Number of Crossing-Free Straight-Edge Graphs and the Number of Triangulations
The Number of Spanning Trees and Forests
The Number of Crossing-Free Straight-Edge Graphs with a Bounded Number of Edges
Conclusion
References
Geometric Computations on Indecisive Points
Introduction
Exact Computations on Indecisive Point Sets
Polynomial Time Algorithms
Hardness Results
Approximate Computations on Uncertain Points
References
Closest Pair and the Post Office Problem for Stochastic Points
Introduction
The Stochastic Closest Pair Problem
Counting Vertex Covers in Unit Disk Graphs
Bichromatic Unit Disk Graphs
Complexity of the Stochastic Closest Pair Problem
Linearly Separable Point Sets under the L Norm
Stochastic Approximate Nearest Neighbor Queries
Approximation via a Modified Distance Function $^~l$
The Data Structure: A BBD Tree
An Exact Query Algorithm for $^~l$
References
Competitive Search in Symmetric Trees
Introduction
Symmetric Tree Traversal
The Case Where All Goals Are Known to Lie at the Same Level
Worst-Case Probe Cost
Average and Expected-Case Probe Cost
Taking Full Search Cost into Consideration
The Case Where Goals May Appear on Many Different Levels
General Symmetric Trees
References
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in $O(diameter · n log n)$ Time
Introduction
Applications
Related Work
Preliminaries
Flow
Quasi-Feasible Flows and Negative-Length Dual Cycles
The Algorithm
Correctness and Analysis
References
Planar Subgraphs without Low-Degree Nodes
Introduction
Orientation Problem on Planar Circuit Networks
Degree One
Degree Two
Degree Three
Augmenting with Bounded Length Edges
Conclusions
References
Constructing Orthogonal de Bruijn Sequences
Introduction
Preliminaries
Kautz Graphs
Analytical Results
Special Orthogonal Families
Counting Eulerians
Heuristic Construction of Orthogonal Sequences
Open Problems
References
A Fast Algorithm for Three-Dimensional Layers of Maxima Problem
Introduction
Sweep Plane Algorithm
Fast Queries, Slow Updates
Additional Staircases
Efficient Algorithms for the Layers-of-Maxima Problem
References
Succinct 2D Dictionary Matching with No Slowdown
Introduction
Overview
Preliminaries
The Algorithm
Pattern Preprocessing
Text Scanning
Conclusion
References
PTAS for Densest $k$-Subgraph in Interval Graphs
Introduction
Preliminaries
Sequence Representations
Simple Sequence Representations
Dynamic Programming
References
Improved Distance Queries in Planar Graphs
Introduction
Preliminaries
Decomposition
The Dense Distance Graph
The Monge Property
Linear-Space Data Structure
Improved Preprocessing Time for $S ? [n4/3, n2]$
Improved Query Time for $S ? [n4/3, n2]$
The Preprocessing Algorithm
The Query Algorithm
References
Piercing Quasi-Rectangles: On a Problem of Danzer and Rogers
Faster Algorithms for Minimum-Link Paths with Restricted Orientations
Introduction
3D Rectilinear Paths
C-oriented Paths in the Plane
Contributions
Rectilinear Paths Amidst Rectilinear Obstacles in $R^3$
Avoiding Reillumination
Filtering
Analysis
$C$-oriented Paths in the Plane
Overview
Definitions and Notation
Flush-Lighting
Straddle-Lighting
Analysis
References
Streaming Algorithms for 2-Coloring Uniform Hypergraphs
Introduction
Open Questions
The Delayed Recoloring Algorithm
An Efficient Streaming Algorithm
Coloring Uniform Hypergraphs with O(n2lnn) Vertices
Streaming and the Lovász Local Lemma
References
Density-Constrained Graph Clustering
Introduction
Quality Measures for Clusterings
Problem Statement
Complexity
Generic Greedy Agglomeration
Merge Behavior
Impact of Clustering Measures on Running Times
Concluding Remarks
References
The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light
Introduction
The MST of Symmetric Disk Graphs
The Range Assignment Problem
Proof Overview
Related Work on Disk Graphs
Structure of the Paper
Preliminaries
The MST of SDGs is Light
The Range Assignment Problem
References
Theory vs. Practice in the Design and Analysis of Algorithms
A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint
Introduction
Related Works
Our Results, Techniques, and Paper Outline
Separations of Items
Partial Search Procedure
Computing $L$ and $U$
FPTAS
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken