Algorithms and Computation : 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings / / edited by Khaled Elbassioni, Kazuhisa Makino

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
• Edizione: 1st ed. 2015.
• Descrizione fisica: 1 online resource (XXII, 793 p. 131 illus.)
• Disciplina: 005.1
• Soggetto topico: Algorithms; Computer science—Mathematics; Discrete mathematics; Computer graphics; Artificial intelligence—Data processing; Numerical analysis; Discrete Mathematics in Computer Science; Computer Graphics; Data Science; Numerical Analysis
• Persona (resp. second.): ElbassioniKhaled; MakinoKazuhisa
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: 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].
• Sommario/riassunto: This book constitutes the refereed proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC 2015, held in Nagoya, Japan, in December 2015. The 65 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 180 submissions for inclusion in the book. The focus of the volume is on the following topics: computational geometry; data structures; combinatorial optimization and approximation algorithms; randomized algorithms; graph algorithms and FPT; computational complexity; graph drawing and planar graphs; online and streaming algorithms; and string and DNA algorithms.
• Titolo autorizzato: Algorithms and Computation
• ISBN: 3-662-48971-6
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910484799203321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 9472