Algorithms and Computation

Name: Algorithms and Computation | 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings
Brand: Springer
Price: 93.08 EUR
Availability: OnlineOnly

26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings

Khaled Elbassioni Kazuhisa Makino(Editor)

Springer (Publisher)

Published on 7. December 2015

XXII, 793 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-48971-0 (ISBN)

€93.08incl. 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 Talks
Soft Clustering: Models and Algorithms
Computing on Strategic Inputs
Lower Bounds on the Size of Linear Programs
Contents
Computational Geometry I
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino
1 Introduction
2 Definitions
2.1 Words
2.2 Factors
2.3 Special Words and Factors
2.4 Polyominoes and Boundary Words
2.5 Tilings
3 The Beauquier-Nivat Criterion
4 A Bound on the Number of Factorizations
5 An Algorithm for Enumerating Factorizations
References
Adaptive Point Location in Planar Convex Subdivisions
1 Introduction
2 Triangulation of a Convex Polygon
3 Point Location in a Convex Subdivision
4 Conclusion
References
Competitive Local Routing with Constraints
1 Introduction
2 Preliminaries
3 Lower Bound on Local Routing
4 Routing on the Constrained 6-Graph
4.1 Positive Routing on the Constrained Half-6-Graph
4.2 Routing on the Constrained 6-Graph
4.3 Negative Routing on the Constrained Half-6-Graph
References
Navigating Weighted Regions with Scattered Skinny Tetrahedra
1 Introduction
2 Preliminaries
3 Placement of Steiner Points
4 Steiner Graph and Snapping
5 Processing Extended Clusters and Vertex Stars
5.1 Locally Shortest Path
5.2 Approximate Shortest Path
References
Data Structures
On the Succinct Representation of Unlabeled Permutations
1 Introduction and Motivation
2 Definitions and Preliminaries
3 Direct Labeling Scheme
4 Succinct Data Structures with Label Space n
5 Succinct Data Structures with Label Space cn1+
6 Lower Bounds
6.1 Lower Bound for Auxiliary Data with Label Space cn
6.2 Lower Bound for Auxiliary Data with Label Space cn1+
7 Applications
8 Conclusion
References
How to Select the Top k Elements from Evolving Data?
1 Introduction
2 Preliminaries
3 Consecutive-Swapping Model
3.1 An Algorithm for the Top-k-set Problem
3.2 An Algorithm for the Top-k-selection Problem
3.3 Lower Bounds for the Top-k-selection Problem
4 Gaussian-Swapping Model
5 Conclusions
References
Optimal Search Trees with 2-Way Comparisons
1 Background and Statement of Results
2 Proof of Spuler's Conjecture
3 Proofs of Theorem1 (Algorithm for 2wcst) and Theorem3
3.1 Perturbation Argument
Proofs of Theorems1 and 3
4 Proof of Theorem2 (Additive-3 Approximation Algorithm)
5 Proof of Theorem4 (Errors in Work on Binary Split Trees)
6 Proof of Theorem5 (O(nlogn) Time Without Equality)
7 Appendix
7.1 Python Code for Theorem4 (gbst Algorithm of [9])
References
Multidimensional Range Selection
1 Introduction
2 Preliminaries
3 The ``Abstract'' Problem
4 Range Selection
5 Dominance Counting and Parallel Counting
References
Combinatorial Optimization and Approximation Algorithms I
On the Minimum Cost Range Assignment Problem
1 Introduction
2 Minimum Cost Range Assignment in 1D
2.1 An Exact Algorithm for the 1D MinRange Problem
2.2 An Exact Algorithm for the 1D MinRangeSpanner Problem
3 The MinRange Problem in Higher Dimensions
3.1 Our Approach
3.2 The Approximation Algorithm
References
On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems
1 Introduction
2 An O(n1/3) Approximation Algorithm for DkCS
2.1 Preliminaries
2.2 Procedure A1: A Trivial Procedure
2.3 Procedure A2: A Greedy Procedure
2.4 Colored Walks of Length 2
2.5 Procedure A4: Another Greedy Procedure
2.6 Algorithm A
2.7 An Algorithm for MIN-REP
3 Reduction from the Densest k-Subgraph (DkS) Problem
References
General Caching Is Hard: Even with Small Pages
1 Introduction
2 Reduction
3 Proof of Correctness
References
Randomized Algorithms I
The Secretary Problem with a Choice Function
1 Introduction
2 Model
3 Algorithm
4 Upper Bounds
References
The Benefit of Recombination in Noisy Evolutionary Search
1 Introduction
2 Preliminaries
2.1 Algorithms
3 Results
3.1 Mutation-Based Approach
3.2 Compact GA
4 Conclusions
References
Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples
1 Introduction
2 Preliminaries
3 Learning k-term DNF from Positive Samples
4 Learning Documents for Steganography
5 Conclusions
References
Combinatorial Optimization and Approximation Algorithms II
Obtaining a Triangular Matrix by Independent Row-Column Permutations
1 Introduction
2 Notations
3 Answering Wilf's Question
3.1 Disproving a Previous Related Result
3.2 Our NP-completeness Proof for Wilf's Question
4 Exponential-Time Algorithm
5 Conclusion
References
Many-to-one Matchings with Lower Quotas: Algorithms and Complexity
1 Introduction
2 Degree- and Quota-restricted Cases
2.1 Problem Definition
2.2 Degree-Restricted Cases
2.3 Quota-Restricted Cases
3 Bounded treewidth graphs
4 Approximation
References
Minimizing the Maximum Moving Cost of Interval Coverage
1 Introduction
2 Preliminaries
3 The Decision Problem
3.1 The Algorithm Description
3.2 The Algorithm Implementation
4 The Optimization Problem
4.1 An Overview
4.2 A General i-th Step
4.3 Maintaining the Algorithm Invariants
References
Randomized Algorithms II
Heuristic Time Hierarchies via Hierarchies for Sampling Distributions
1 Introduction
2 Preliminaries
3 Hierarchy for
4 Conditional Hierarchy
5 Hierarchy for k-valued Functions
6 Hierarchy for Arbitrary Distributions
7 Hierarchy for
References
Unbounded Discrepancy of Deterministic Random Walks on Grids
1 Introduction
2 Preliminaries
3 Stable Configuration of the Rotor-Router Model
4 Conclusion
References
Trading off Worst and Expected Cost in Decision Tree Problems
1 Introduction
2 Trade-off: Upper Bound
3 Trade-off: Lower Bound
3.1 The Structure of the Instance I in Theorem ??
3.2 Proof of Theorem ??
4 Open Problems
References
Graph Algorithms and FPT I
Sliding Token on Bipartite Permutation Graphs
1 Introduction
1.1 Preliminaries
2 Coping with Rigid Tokens
3 An Algorithm on Bipartite Graphs
4 Sliding Token on Bipartite Permutation Graphs
5 Sliding Token on Bipartite Distance-Hereditary Graphs
6 Discussion
References
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width
1 Introduction
2 Definitions and Preliminaries
3 Enumerations for Graphs of Bounded LMIM-width
4 Enumeration of Minimal Dominating Sets for Unit Square Graphs
References
Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
1 Introduction
2 Upperbounds on the Local Minimum Degree
3 Parameterized Complexity
4 Exponential Algorithms
5 Conclusion
References
Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
1 Introduction
2 Preliminaries
3 FPT Algorithm for p-CFC
4 Exact Algorithm for Max-Conflict Free Coloring
References
Computational Geometry II
Geometric Matching Algorithms for Two Realistic Terrains
1 Introduction
1.1 Our Results
2 Translation Space Under L Metric
2.1 Candidate Pairs Defining the Distance Between Two Terrains
2.2 Subdividing Translation Space
2.3 Complexity of the Subdivision M
3 Geometric Matching Algorithms Under L Metric
3.1 Construction of M
3.2 A Deterministic Geometric Matching Algorithm
3.3 A Randomized Geometric Matching Algorithm
4 Geometric Matching Algorithm Under L1 Metric
References
Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability
1 Introduction
2 Definitions
2.1 Tiles, Assemblies, and Supertiles
2.2 The Assembly Process
2.3 Two-Handed Tile Assembly Systems
2.4 Size-Dependent Systems
3 Constant-Height Rectangles
4 Squares
5 -stabilility is coNP-complete
6 Open Problems
References
The 2-Center Problem in a Simple Polygon
1 Introduction
2 Preliminary
3 The Partition by an Optimal 2-center
3.1 Computing a Set of Candidate Edge Pairs
4 A Decision Algorithm for a Candidate Edge Pair
4.1 Computing the Intersection of Geodesic Disks
4.2 Subdividing the Edges and the Chains
4.3 Four Coverage Functions and Their Extrema
4.4 Computing a 2-center for a Pair of Subchains
4.5 The Analysis of the Decision Algorithm
5 An Optimization Algorithm for a Candidate Edge Pair
5.1 Computing the Coverage Function Values
5.2 Constructing 4-Tuples Consisting of Two Cells and Two Subedges
References
Choice Is Hard
1 Introduction
2 A New Satisfiability Result
3 Applications of LSAT to Rainbow Problems
3.1 Rainbow Minmax Gap (Decision Version) is NP-complete
3.2 Rainbow Piercing and Rainbow Covering are NP-complete
4 Exact Coverage of Color Classes
4.1 Unit Intervals
4.2 Arbitrary Length Intervals
References
Graph Algorithms and FPT II
Fully Dynamic Betweenness Centrality
1 Introduction
2 The Fully Dynamic Betweenness Centrality Algorithm
3 Background
3.1 The NPR Decremental APASP Algorithm [19]
3.2 The DI Fully Dynamic APSP Algorithm [8]
4 Overview of Our Fully Dynamic APASP Approach
5 Algorithm fully-dynamic
6 Algorithm ffd
7 Conclusion
References
When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots
1 Introduction
2 Idleness of Line Segments
2.1 The Upper Bound
2.2 The Lower Bound
3 Idleness of Arbitrary Graphs
3.1 A General Result and Algorithm
3.2 Hardness of Computing the Idleness
3.3 Characterizing Graphs with Minimum Idle Time
4 Conclusion and Open Problems
References
Cops and Robbers on String Graphs
1 Introduction
2 Outer-String Graphs
3 Guarding Shortest Paths and Curves in String Graphs
4 Capturing Robber in String Graphs
5 String Graphs on Bounded Genus Surfaces
6 Conclusions
References
Min-Power Covering Problems
1 Introduction
2 Min-Power-Cover Vertex Cover
2.1 A 2-Approximation Algorithm for the Asymmetric Case
2.2 A Faster 2-Approximation Algorithm for Symmetric Case
2.3 A Polynomial Case: Bipartite Graphs
3 Min-Power-Cover Cut
3.1 Directed Graphs
3.2 Undirected Graph
4 Min-Power-Cover Spanning Tree
5 Min-Power-Cover Path
6 Concluding Remarks
References
Computational Geometry III
Minimizing the Diameter of a Spanning Tree for Imprecise Points
1 Introduction
1.1 Our Results
2 Preliminary
3 Monopolar Case
4 Bipolar Case
4.1 Bipolar Tree Topologies
4.2 Locations of an Optimum Placement
5 Disjoint Disks
6 Unit Disks
6.1 Separable Bipolar Tree Topologies
6.2 Computing Farthest Voronoi Diagrams in a Batch
References
Model-Based Classification of Trajectories
1 Introduction
2 Dynamic Programming for Discrete Parameter
3 NP-hardness for Continuous Parameter
4 Polynomial-Time Algorithm for Realistic Inputs
References
Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
1 Introduction
2 Preliminaries and Definitions
3 The Farthest Voronoi Diagram of a Sequence
3.1 Deletion and Insertion of Arcs
4 A Randomized Linear Construction
5 A Deterministic Linear Divide-and-Conquer Algorithm
References
Unfolding Orthogonal Polyhedra with Linear Refinement
1 Introduction
2 Preliminaries
3 The Unfolding Tree
4 The Linear Refinement Unfolding Algorithm
References
Combinatorial Optimization and Approximation Algorithms III
Colored Non-crossing Euclidean Steiner Forest
1 Introduction
2 Algorithms for k-CESF
3 PTAS for 2-CESF
4 Algorithm for 3-CESF
5 Conclusion
References
On a Generalization of Nemhauser and Trotter's Local Optimization Theorem
1 Introduction
2 Notation System
3 The Decomposition Techniques
4 Algorithms
4.1 The Algorithm for Decompositions
4.2 The Algorithm for Theorem??
5 Concluding Remarks
References
Approximation Algorithms in the Successive Hitting Set Model
1 Introduction
1.1 Related Work
1.2 Contribution
2 Preliminaries
3 Greedy Algorithm for General Set Systems
3.1 Successive Greedy
3.2 Approximation Quality
4 Pricing Method for the K-Hitting Set Problem
4.1 Successive Algorithm
4.2 Correctness and Analysis
5 Concatenated Hitting Sets
5.1 Successive Algorithm
5.2 Correctness and Approximation Quality
6 Applications
7 Experiments
8 Conclusions and Future Work
References
Randomized Algorithms III
Generating Random Hyperbolic Graphs in Subquadratic Time
1 Introduction
2 Related Work and Preliminaries
2.1 Existing Graph Generators
2.2 Graphs in Hyperbolic Geometry
2.3 Poincaré Disk Model
3 Fast Generation of Graphs in Hyperbolic Geometry
3.1 Generation Algorithm
3.2 Time Complexity
4 Experimental Evaluation
4.1 Results
5 Conclusions
References
Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
1 Introduction
1.1 Related Work
1.2 Contribution
2 Preliminaries
2.1 Contraction Hierarchies
2.2 Randomized Skip Lists
2.3 Our Model: Graph Metrics with Bounded Growth
3 Randomized Contraction Hierarchies
3.1 Preprocessing
3.2 Analysis
4 Experimental Results
5 Conclusions
References
Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
1 Introduction
2 Definitions
3 Results
3.1 Discrete Scenario Uncertainty
3.2 Interval Uncertainty
3.3 Convex Uncertainty
4 Conclusion
References
Computational Geometry IV
An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
1 Introduction
2 Obtaining Chirotopes from Radial Systems
2.1 Obtaining Hull Edges
2.2 Obtaining the Actual Hulls from a Hull Structure
References
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
1 Introduction
2 Preliminaries
3 The Approximate Decider
3.1 Solving the Free-Space Region Problem on Pieces
4 On One-Dimensional Separated Curves
4.1 Greedy Decider for One-Dimensional Separated Curves
4.2 Solving the Reduced Free-Space Problem
5 Conclusion
References
Computing the Gromov-Hausdorff Distance for Metric Trees
1 Introduction
2 Preliminaries
3 Hardness of Approximation
4 Relating Gromov-Hausdorff and Interleaving Distances
5 Computing the Interleaving Distance
6 Conclusion
References
The VC-Dimension of Visibility on the Boundary of a Simple Polygon
1 Introduction
2 Preliminaries
3 VC-Dimension Upper Bound Proof
References
Computational Complexity I
Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)
1 Introduction
1.1 Our Contribution
1.2 Techniques and Proof Overview
1.3 New Issues Raised by Quantum Binding in Security Analysis
1.4 Related Work
2 Preliminaries
3 Formalization and Construction of QBC
4 From QBC to QZK
References
Effectiveness of Structural Restrictions for Hybrid CSPs
1 Introduction
2 Preliminaries
2.1 Fixed Template CSP
2.2 Fixed Template VCSP
2.3 Polymorphisms
2.4 Algebraic Dichotomy Conjecture
2.5 Hybrid (V)CSP Setting
3 Our Results
3.1 Implications of Theorems 2, 3 and 4
References
Polynomial-Time Isomorphism Test of Groups that are Tame Extensions
1 Introduction
2 Preliminaries
3 The divide and conquer strategy for Problem1
4 Overview of Algorithms for ActComp and CCIso
5 Discussion
References
Quantum Algorithm for Triangle Finding in Sparse Graphs
1 Introduction
2 Preliminaries
2.1 Query Complexity for Graph-Theoretic Problems
2.2 Quantum Algorithm for Dense Triangle Finding
3 Quantum Algorithm for Sparse Triangle Finding
References
Graph Drawing and Planar Graphs
On Hardness of the Joint Crossing Number
1 Introduction
2 Basic Concepts
3 Face-Anchored Joint Embeddings
4 Multiplying Face Anchors
5 Reduction from Anchored Planar Crossing Number
6 Conclusions
References
An O(n) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs
1 Introduction
2 Preliminaries
2.1 Class nSC and its properties
3 Reachability in Layered Planar Graphs
3.1 The Auxiliary Graph H
3.2 Description of the Algorithm
References
Constant Query Time (1+)-Approximate Distance Oracle for Planar Graphs
1 Introduction
2 Preliminaries
3 Oracle with Additive Stretch
4 Oracle with (1+) Stretch
5 Concluding Remarks
References
Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
1 Introduction
2 Preliminaries
3 NP-Completeness for Graphs with Cycles
4 Trees
4.1 2-Approximation Using Multicut
4.2 Optimal Solution
5 Triangulations
References
Computational Complexity II
A New Approximate Min-Max Theorem with Applications in Cryptography
1 Introduction
1.1 The Min-Max Theorem
1.2 Switching the Order of Quantifiers by the Min-Max Theorem
1.3 Our Contribution
1.4 Related Works
2 Applications
2.1 Impagliazzo Hardcore Lemma
2.2 A (new) Optimal Hardcore Lemma for Metric Pseudoentropy and Applications to Transformations
2.3 A (fixed) Construction of a Simulator for Auxiliary Inputs
2.4 More Applications
References
Give Me Another One!
1 Introduction
2 Preliminaries
3 Results
4 Duality and Inapplicability of Clone Closure
5 Finding Another Solution Closest to the Given One
5.1 Polynomial-Time Cases
5.2 Hard Cases
6 Concluding Remarks
References
On the Complexity of Computing Prime Tables
1 Introduction
2 Background and Related Work
3 Fast Algorithms for Atkin's Sieve
3.1 Atkin's Sieve in O(nlog2 n/loglogn)
3.2 Atkin's Sieve in O(M(n logn))
4 Lower Bound
5 Conclusion
References
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
1 Introduction
1.1 Black-White Poset Games
1.2 Generalized Col
1.3 Nim on Graphs
2 PSPACE-Completeness of Black-White Poset Games
2.1 Construction
2.2 Strategy
3 Generalized Col is PSPACE-Complete
3.1 Preliminaries
3.2 Main Construction
4 Black-White NimG on Undirected Graphs is in ¶
5 Conclusions and Open Problems
References
Online and Streaming Algorithms
Run Generation Revisited: What Goes Up May or May Not Come Down
1 Introduction
2 Up-Down Run Generation
3 Structural Properties
4 Up-Down Replacement Selection
5 Run Generation with Resource Augmentation
6 Offline Algorithms for Run Generation
7 Run Generation on Nearly Sorted Input
8 Conclusion and Open Problems
References
Streaming Verification in Data Analysis
1 Introduction
2 Preliminaries
3 Rectangular Matrix Multiplication and Eigenstructure
4 Shape Analysis in a Few Rounds
5 SIPs for General Clustering Problems
References
All-Around Near-Optimal Solutions for the Online Bin Packing Problem
1 Introduction
1.1 Contribution
2 Harmonic Match Algorithm
2.1 Worst-Case Analysis
2.2 Average-Case Analysis
3 Refined Harmonic Match
3.1 Worst-Case Analysis
3.2 Average-Case Analysis
4 Experimental Evaluation
5 Remarks
References
Serving Online Requests with Mobile Servers
1 Introduction
1.1 Related Work
2 Problem Statement
2.1 Objective Functions
2.2 Service Cost Function Properties
3 Contributions
4 Minimizing the Number of Movements
5 Minimizing Movements and Service Cost
5.1 Algorithm Description
5.2 Analysis Overview
5.3 Lower Bound
6 Future Work
References
String and DNA Algorithms
An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
1 Introduction
1.1 Prior Work and Our Contribution
2 Preparation
3 The High-Level Picture
4 Finding k-mismatch LSUS
4.1 Finding Exact LSUS (k=0)
4.2 Finding Approximate LSUS (k 1)
5 Finding k-mismatch SLS
6 Finding k-mismatch SUS
References
Inferring Strings from Full Abelian Periods
1 Introduction
2 Preliminaries
3 Algorithms
3.1 New Properties on Full Abelian Periods
3.2 Inferring the Lexicographically Smallest String
3.3 Enumerating S(n, D, )
3.4 Enumerating S'(n, D, )
References
Toehold DNA Languages are Regular (Extended Abstract)
1 Introduction
2 Model
3 DNA Algorithms
4 Regular DNA Algorithms
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Algorithms and Computation

Description

More details

Other editions

Additional editions

Content

System requirements