Algorithms and Computation

Name: Algorithms and Computation | 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings

Takao Asano Shin-ichi Nakano Yoshio Okamoto Osamu Watanabe(Herausgeber*in)

Springer (Verlag)

Erschienen am 3. Dezember 2011

XVIII, 775 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-25591-5 (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

Intro
Title page
Preface
Organization
Table of Contents
Invited Talk I
Algorithm Engineering for Route Planning- An Update -
References
Invited Talk II
Semidefinite Programming and Approximation Algorithms: A Survey
References
Approximation Algorithms I
The School Bus Problem on Trees
Introduction
Our Results
Related Work
Preliminaries
A 4-Approximation to the SBP on Trees
A 12.5-Approximation to the Uncapacitated SBP-R on Trees
References
Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph
Introduction
Shallow-Light Steiner Trees
An O(logn)-Approximation for the (k, 2)-Subgraph Problem
References
Improved Approximation Algorithms for Routing Shop Scheduling
Introduction
Previous Work
Our Results and Techniques
Preliminaries
Routing Open Shop
Routing Flow Shop
References
Contraction-Based Steiner Tree Approximations in Practice
Introduction
History
Contraction Framework
Algorithm Engineering
Experiments
Conclusions and Thoughts
References
Computational Geometry I
Covering and Piercing Disks with Two Centers
Introduction
Intersecting Disks with Two Centers
Decision Algorithm
Optimization Algorithm
Covering Disks with Two Centers
The General Case
The Restricted Case
References
Generating Realistic Roofs over a Rectilinear Polygon
Introduction
Preliminaries
Properties of Realistic Roofs
Local Properties of Valleys and Ridges
Global Structure of Realistic Roofs
Enumerating Realistic Roofs and Computing Optimal Roofs
References
Computing the Visibility Polygon Using Few Variables
Introduction
Preliminaries
An O(n) Algorithm Using O(1) Variables
An O(n logr) Algorithm Using O(logr) Variables
Closing Remarks
References
Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius
Introduction
Definitions and Results
Layered Nearest Neighbor Algorithm
Bounded Radius Network
Conclusion
References
Graph Algorithms
Hamiltonian Paths in the Square of a Tree
Introduction
Caterpillars and Horsetails
2H-Paths in (u,v)-Horsetails
Efficient Algorithm for Horstail Queries
References
Dominating Induced Matchings for P7-free Graphs in Linear Time
Introduction and Basic Notions
Simple Properties of Graphs with Dominating Induced Matching
Structure of P7-free Graphs with Dominating Induced Matching
Distance Levels with Respect to an M-Edge in a P3
Edges in and between Ti and Tj, i =j
The Algorithm for the General P7-free Case
Conclusion
References
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
Introduction
Preliminaries
Set-Restricted Disjoint Paths
Contractions and Induced Minors in Chordal Graphs
Concluding Remarks
References
Recognizing Polar Planar Graphs Using New Results for Monopolarity
Introduction
Hardness Results
A 2-SAT Approach and a Superclass of Chair-Free Graphs
A Superclass of Hole-Free Graphs
Some Efficiently Solvable Cases of Polarity for Planar Graphs
Conclusion
References
Robustness of Minimum Cost Arborescences
Introduction
Fulkerson's Algorithm
A Sufficient Condition is Necessary
A Necessary Condition is Sufficient
References
Data Structures I
Path Queries in Weighted Trees
Introduction
Previous Work
Our Results
Properties of Ordinal Trees
A Pointer Machine Data Structure
Optimizations in the RAM model
Linear Space, but Slower Reporting
Slightly More Space, Much Faster Reporting
References
Dynamic Range Majority Data Structures
Introduction
Previous Work
Our Results
Dynamic Data Structures in One Dimension
Supporting Queries
Supporting Updates
Speedup for Integer Coordinates
Dynamic Data Structures in Higher Dimensions
References
Dynamic Range Selection in Linear Space
Introduction
Previous Work
Our Results
Linear Space Data Structure
Space Efficient Ranking Trees
Answering Queries
Handling Updates
Dynamic Arrays
Concluding Remarks
References
A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
Introduction
A Data Structure with Optimal Query Time
Compact Representation
References
Encoding 2D Range Maximum Queries
Introduction
Random Input
Small m
Data Structures for 2D-RMQ
Conclusions and Open Problems
References
Distributed Systems
Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions
Introduction
Precise Model and Results
The Diameter of the Largest Connected Component
References
Broadcasting in Heterogeneous Tree Networks with Uncertainty
Introduction
Preliminaries
Finding a Minmax-Regret Broadcast Center
Correctness
Time Complexity
Conclusion
References
Optimal File Distribution in Peer-to-Peer Networks
Introduction
Homogeneous Symmetric Capacities
Heterogeneous Symmetric Capacities
References
Computational Geometry II
Animal Testing
Introduction
Algorithm 1 Based on Fundamental Polygonsand Davenport-Schinzel Sequences
Algorithm 2 Based on Euler-Poincaré Formula
References
Cutting Out Polygons with a Circular Saw
Introduction
Preliminaries
Algorithm
References
Fast Fréchet Queries
Introduction
Preliminaries
The Data Structure
Making Part of the Query
Relative Error
References
Graph Drawing and Information Visualization
Angle-Restricted Steiner Arborescences for Flow Map Layout
Introduction
Optimal Flux Trees
Spiral Trees
Computing Spiral Trees
Approximating Spiral Trees in the Presenceof Obstacles
Rectilinear Steiner Arborescences
Spiral Trees
References
Treemaps with Bounded Aspect Ratio
Introduction
Convex Treemaps
Ortho-Convex Treemaps
Conclusions
References
Simultaneous Embedding of Embedded Planar Graphs
Introduction and Overview
Preliminaries
Computing a Sefe-Fe of Three Embedded Planar Graphs
Sefe-Fe and Sge-Fe of k Embedded Graphs Is NP-Hard
References
Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations
Introduction
Representations for Maximal Planar Graphs
Representations of Planar 3-trees
Representations for Maximal Outer-Planar Graphs
Conclusion
References
Data Structures II
Fully Retroactive Approximate Range and Nearest Neighbor Searching
Introduction
Related Work
Our Results
A General Approach to Retroactivity
Main Results
References
Compact Representation of Posets
Introduction
Our Work in Context
Contributions
Preliminaries
Posets
Transitive Reductions
Succinct Data Structures
The Representation
Storing the Chains
Storing the Order Relation between Chains
Operations
Operation reachability(x,y)
Operations succG(x) and predG(x)
Operation range(x,y)
Operation adjGr(x,y)
Operations succGr(x) and predGr(x)
Operations a-succGr(x) and a-predGr(x)
Operations LUB(x1, ., xt) and GLB(x1, ., xt)
Operations a-LUB(x1, ., xt) and a-GLB(x1, ., xt)
Summary and Open Questions
References
Explicit Array-Based Compact Data Structures for Triangulations
Introduction
Existing Mesh Data Structures
Preliminaries
Compactly Representing Triangulations
The First Data Structure: Simple and Still Redundant
More Compact Solutions, via Minimal Schnyder Woods
Further Reducing the Space Requirement
Experimental Results
References
Space-Efficient Data-Analysis Queries on Grids
Introduction
Wavelet Trees
Representation of Grids
Dynamism
Statistical Queries
Range Sum, Average, and Variance
Range Minima and Maxima
Range Median and Quantiles
Range Majority
Range Successor and Predecessor
Dynamism
Final Remarks
References
Parameterized Algorithms I
A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
Introduction
Preliminaries
Modular Partitions
Reductions and Kernel
Data Reduction Rules
Analysis of Kernel Size
Conclusion
References
Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
Introduction
Preliminaries
Canonical Sequence for Acyclic Bipartite Tournament
Allying Sequence of Node Sets and Increasing Subsequence of Node Sets
Consistent Node Sequence and Compatible Node Sequence
A Reduction
Framework of Our Proof for the Main Lemma
Good Sequence
Framework for Proving the Main Lemma
Dynamic Programming for Proving Lemma 4
References
Parameterized Algorithms for Inclusion of Linear Matchings
Introduction
Problem Definition
Algorithms for Linear Matching Inclusion
An FPT Algorithm for Parameters d and k
An FPT Algorithm for Parameter p
An Algorithm for Nesting-Free Patterns
Hardness Results
Hardness of Linear Matching Inclusion
Hardness of Nesting-Free 2-Interval Pattern
References
Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem
Introduction
Preliminaries
Algorithms Implemented
Computational Results
Results for Longest Paths
Results for Grid/Cylinder Minors
Concluding Remarks
References
Parallel and External Memory Algorithms
Sorting, Searching, and Simulationin the Map Reduce Framework
Introduction
Algorithmic Framework for I/O-memory-bound MapReduce
Simulation Results
Prefix Sums and Random Indexing
Multi-searching and Sorting
References
External-Memory Multimaps
Introduction
External-Memory Cuckoo Hashing
External-Memory Multimaps
Experiments
References
External Memory Orthogonal Range Reporting with Fast Updates
Introduction
Three-Sided Range Reporting for B=(logB4 N)
Two-Dimensional Range Reporting for B=(log24 N)
Two-Dimensional Range Reporting for small B
References
Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization
Introduction
Preliminaries
Previous Work
Sorting
Shortest Paths
Eulerian Cycles
Conclusions
References
Game Theory and Internet Algorithms
Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs
Introduction
Preliminaries
PageRank Values
Directed PageRank games
Undirected PageRank Games
Trees
General Graphs
Conclusion
References
Improved Collaborative Filtering
Introduction
Preliminaries
Algorithm S: Linear Dependence on D
Complexity Independent of D
References
Asymptotic Modularity of Some Graph Classes
Introduction
Revisiting Modularity
Modularity of Decomposable Graphs
Decomposable graphs
Multidimensional Torus
Hypercube
Unit Ball Graph of a Bounded Growth Metric
Bounded Growth Metrics
R-Nets
Modularity of an R-Net Clustering
Constant Average Degree Graphs
Trees of Small Maximum Degree
Graphs of Average Degree d
Power-Law Graphs
Conclusion
References
Computational Complexity
Program Size and Temperature in Self- assembly
Introduction
Abstract Tile Assembly Model
Finding Strengths to Implement a Tile System
Finding the Minimum Tile Assembly System Assembling a Square at any Temperature
Bounds on Temperature Relative to Number of Tile Types
Tile Assembly Systems Requiring Temperature Exponential in Number of Tile Types
Temperature Linear in the Number of Tile Types Suffices for 2-Cooperative Equivalence
Open Questions
References
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems
Maximization by Multiplicative Measure
Formal Definitions and Basic Properties
Constraints and Relations
Optimization Problems with Multiplicative Measures
Tmax-Constructibility
Proof of the Main Theorem
First Step Toward the Proof
Second Step Toward the Proof
References
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic
Introduction
Preliminaries
DPLL Algorithms with a Cut Heuristic
Distribution
Boundary Expanders and the Closure
Refined Splitting Tree
References
Approximation Algorithms II
Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2- Dimensional Plane
Introduction
Problem Formulations and Algorithm
North-West Corner Rule and Dependent Rounding
Analysis of Approximation Ratio
Conclusion
References
Packing-Based Approximation Algorithm for the k-Set Cover Problem
Introduction
Algorithm Description and the Main Theorem
The Restricted k-Set Packing Algorithm
Blocking
Analysis of the Restricted 4-Set Packing Algorithm
Analysis of the Restricted k-Set Packing Algorithm, k5
Analysis of the Algorithm PRPSLI
References
Capacitated Domination: Constant Factor Approximations for Planar Graphs
Introduction
Preliminary
Constant Approximation for Outer-Planar Graphs
The Structure
Removing More Edges
Greedy Charging Scheme
Overall Analysis
Extension to Planar Graphs
Conclusion
References
Randomized Algorithms
On Power-Law Distributed Balls in Bins and Its Applications to View Size Estimation
Introduction
Context
Model
Our Contribution
Bounds for the Expected Number of Balls Needed to Fill All Bins
Stochastic Majorization Scheme for Finding Bounds
General Bounds When n1
Asymptotically Accurate Estimator for the Expected Number of Balls
Estimating the Expected Number of Occupied Bins Given a Fixed Number of Balls
Lower Bound
Upper Bound
Bound Performance
Conclusion
References
A Randomized Algorithm for Finding Frequent Elements in Streams Using O (log logN) Space
Introduction
Preliminary
Problem Description
A Basic Idea
Algorithm
Other Naïve Algorithms
Concluding Remark
References
A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
Introduction
Adaptive, Non-adaptive, and Canonical Testers
Graph Blow-Ups and Blow-Up Collections
Organization of the Paper
Notation and Basics
Adaptively Testing BUC(H) Given a Promise
Proof of Lemma 11
Non-adaptively Testing BUC(H) Given a Promise
Removing the Low-Degree Promise
Conclusions
References
Online and Streaming Algorithms
Online Linear Optimization over Permutations
Introduction
Preliminaries
Algorithm
Main Structure
Projection
Decomposition
Main Result
Experimental Results
Conclusion
References
On the Best Possible Competitive Ratio for Multislope Ski Rental
Introduction
Problem Statement and Preliminaries
Infimum of the Best Possible Competitive Ratio
Supremum of the Best Possible Competitive Ratio
Subclasses of the Multislope Ski Rental
References
Input-Thrifty Extrema Testing
Introduction
Input-Thrifty Algorithms
The Uncertainty Model
Competitive Analysis
Extrema Testing
Preliminaries
Related Work
The List Traversal Model
Intrinsic Cost
Hyperbolic Sweep
Conclusion
References
Edit Distance to Monotonicity in Sliding Windows
Introduction
Formal Problem Definitions
A (4+)-Approximate Algorithm for Estimating ED
Estimating R(i)
Lower Bounds for Out-of-Order Streams
Estimating ED in an Out-of-Order Stream
Estimating LIS in an Out-of-Order Stream
References
Computational Geometry III
Folding Equilateral Plane Graphs
Introduction
Locked Trees: Not If Equilateral and Linear
Single-Vertex Origami: Generalization
Definitions
Linear Equilateral Trees
Flat-Foldable Planar Graphs
NP-Hardness of Graph Folding
References
Efficient Algorithms for the Weighted k-Center Problem on a Real Line
Introduction
The Algorithmic Scheme
The Data Structure for Answering (i,j) Queries
Problem Modeling and Observations
The Data Structure
References
Outlier Respecting Points Approximation
Introduction
Statements of Problems
Our Results
The Algorithmic Framework
Algorithmic Components for the Problem RVWSF
Algorithmic Components for RVPF and RVWPF
References
An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles
Introduction
Preliminaries
The Triangle Witness Algorithm
An Improved Triangle Witness Algorithm
References
Parameterized Algorithms II
The Parameterized Complexity of Local Search for TSP, More Refined
Introduction
Basic Notation and Distance Measures
General Graphs
Planar Graphs
Conclusion
References
On the Parameterized Complexity of Consensus Clustering
Introduction
A Search Tree Algorithm for the Average Mirkin Distance
NP-Hardness for Input Partitions with a Bounded Number of Clusters
Hardness of Local Search
Conclusion
References
Two Fixed-Parameter Algorithms for the Cocoloring Problem
Introduction
Background and Notation
(q,q-4)-Graphs
Graphs with Bounded Treewidth
References
Parameterized Complexity of the Firefighter Problem
Introduction
Preliminaries
Parameterized Tractability
Kernelization Feasibility
Conclusion
References
String Algorithms
Faster Approximate Pattern Matching in Compressed Repetitive Texts
Introduction
Block Graphs
Fast Random Access in Compressed Space
Accelerated Approximate Pattern Matching
Conclusions and Future Work
References
A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria
Introduction
Preliminaries
Similarity Criteria
Algorithm
Conclusions
References
Succinct Indexes for Circular Patterns
Introduction
Preliminaries
Circular Burrows-Wheeler Transform
Framework for Circular Dictionary Matching
Succinct Encoding of Circular Suffix Tree
Parentheses Encoding of STc
Height Array
Circular Dictionary Matching with Our Index
References
Range LCP
Introduction
An Algorithm Linear in the Range Length
Finding the Pair with the Longest Common Prefix
An Efficient Range LCP Algorithm
Constructing the Optimal Bridges
Finding the Smallest Bridge in an Interval
References
Optimization
Computing Knapsack Solutions with Cardinality Robustness
Introduction
NP-Hardness for the Max-Robust Knapsack Problem
Simple Pseudo-Polynomial Time Algorithm
Improved Pseudo-Polynomial Time Algorithm
Fully Polynomial Time Approximation Scheme
References
Max-Throughput for (Conservative) k-of-n Testing
Introduction
Related Work
Problem Definitions
The Algorithm for the MinCost Problem
The Algorithm for the CMT(k) Problem
The Equal Rates Case
The Equalizing Algorithm of Condon et al.
An Equalizing Algorithm for the CMT(k) Problem
An Ellipsoid-Based Algorithm for the SMT(k) Problem
References
Closest Periodic Vectors in Lp Spaces
Introduction
Preliminaries
Closest Periodic Vectors in L1, L2 and L Spaces
Closest Periodic Vector in L2 Space
Closest Periodic Vector in L Space
Closest Periodic Vector in L1 Space
Fast Approximations of the Closest Periodic Vector in L1, L2 and L Spaces
Approximation in L2 Space
Approximation in L1 Space
Approximation in L Space
References
Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
Introduction
The Algorithm
Experiments
NP-Completeness
References
Computational Biology
Finding Maximum Sum Segments in Sequences with Uncertainty
Introduction
Notation and Preliminaries
The Length-Relaxed MSSU Problem
Preprocessing
Basic Algorithm
Improved Algorithm
The Length-Constrained MSSU Problem
Concluding Remarks
References
Algorithms for Building Consensus MUL-trees
Introduction
Definitions
Our Results and Organization of the Paper
Preliminaries
Building a Strict Consensus MUL-tree
Building a Majority Rule Consensus MUL-tree
Building a Singular Majority Rule Consensus MUL-tree
References
Adaptive Phenotype Testing for AND/OR Items
Introduction
Our Contributions
Preliminaries
APT Algorithms for General k and d
One Phenotype (k = 1, d 1)
Multiple Phenotype (k 2 and d 1)
APT Algorithms for Special k and d
k = 1 and d = 2
k 1 and d = 1
k = 2 and d = 2
Conclusions
References
An Index Structure for Spaced Seed Search
Introduction
Preliminaries
Definitions and Notations
Search Method
Constructing the b-Suffix Array for Given T and b
Underlying Ideas
O(gn)-Time, O(n)-Space Algorithm
O(wnlogw)-Time and O(wn)-Space Algorithm
Constructing b-Suffix Arrays for Periodic b
Conclusion
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken