Coverart for item
The Resource Algorithm Theory - SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings

Algorithm Theory - SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings

Label
Algorithm Theory - SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings
Title
Algorithm Theory - SWAT 2014
Title remainder
14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings
Creator
Contributor
Language
eng
Member of
Cataloging source
MiAaPQ
Literary form
non fiction
Nature of contents
dictionaries
Series statement
Lecture Notes in Computer Science / Theoretical Computer Science and General Issues
Series volume
v.8503
Algorithm Theory - SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings
Label
Algorithm Theory - SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings
Link
http://libproxy.rpi.edu/login?url=https://ebookcentral.proquest.com/lib/rpi/detail.action?docID=3093381
Publication
Copyright
Related Contributor
Related Location
Related Agents
Related Items
Carrier category
online resource
Carrier category code
cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
txt
Content type MARC source
rdacontent
Contents
  • Preface -- Organization -- The Power of Iterated Rounding -- Orientations and Decompositions of Graphs -- Fast and Powerful Hashing using Tabulation -- Table of Contents -- I/O-Efficient Range Minima Queries -- 1 Introduction -- 2 Lower Bound In Both Models -- 3 Solution in the External Memory Model -- 4 Solution in the Cache-Oblivious Model -- 5 Additional Improvements -- 6 Conclusions -- References -- Online Makespan Minimization with Parallel Schedules -- 1 Introduction -- 2 Reducing MPS to MPSopt -- 3 A(1+f)-Competitive Algorithm for MPSopt -- 4 A(4/3 + f)-Competitive Algorithm for MPSopt -- 5 Algorithms for MPS -- 6 Lower Bounds -- References -- Expected Linear Time Sorting for Word Size ](log2 n log log n) -- 1 Introduction -- 2 Algorithm -- 3 Tools -- 4 Algorithm - RAM Details -- 5 Packed Sorting -- 6 General Sorting -- References -- Amortized Analysis of Smooth Quadtrees in All Dimensions -- 1 Introduction -- 1.1 The Smooth Quadtree Model -- 1.2 Our Results -- 1.3 Related Work -- 1.4 Other Results -- 1.5 Neighbor Pointers without Smoothing -- 2 Analysis of Forcing Chains -- 2.1 Basic Terminology -- 2.2 Forcing Chains -- 2.3 Analysis of 2-Link Chains -- 2.4 Monotonicity in Smooth Subdivisions -- 3 Amortized Bounds for Smooth Splits -- 3.1 Potential of Subdivision Tree -- 3.2 Lower Bound on Smooth Split Complexity -- 4 Conclusion -- References -- New Approximability Results for the Robust k-Median Problem -- 1 Introduction -- 2 Preliminaries -- 3 Hardness of Robust k-Median on Uniform Metrics -- 3.1 Integrality Gap -- 3.2 Reduction from r-Hypergraph Label Cover to Minimum Congestion Set Packing -- 3.3 Analysis -- 4 Hardness of Robust k-Median on Line Metrics -- 5 Conclusion and Future Work -- References -- Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs -- 1 Introduction -- 2 Background -- 2.1 Edge Directions
  • 2.2 Edge Labels -- 3 Barnette's Theorem via the Canonical Ordering -- 4 OnGr{u00A8}unbaum's Conjecture -- 4.1 Putting It All Together -- 5 Conclusion -- References -- Approximating the Revenue Maximization Problem with Sharp Demands -- 1 Introduction -- 2 Model and Preliminaries -- 3 A Pricing Scheme for Monotone Allocation Vectors -- 4 Results for Generic Instances -- 4.1 Inapproximability Result -- 4.2 The Approximation Algorithm -- 5 Results for Proper Instances -- 5.1 Computing an h-Prefix of I of Maximum Revenue -- 5.2 The Approximation Algorithm -- References -- Reconfiguring Independent Sets in Claw-Free Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Equivalence of Sliding and Jumping -- 4 Nonmaximum Independent Sets -- 5 Resolving Cycles -- 6 Summary of the Algorithm -- 7 Discussion -- References -- Competitive Online Routing on Delaunay Triangulations -- 1 Introduction -- 2 Routing on Delaunay Triangulations of Points in General Position -- 2.1 (4s {u221A} 3) {u2248} 21.766-Competitive Online Routing -- 2.2 17.982-Competitive Online Routing -- 2.3 (s(5s + 4)/4) {u2248} 15.479-Competitive Online Routing -- 3 (11+3 {u221A} 2)/2 {u2248} 7.621-Competitive Online Routing for Points in Convex Position -- References -- Optimal Planar Orthogonal Skyline Counting Queries -- 1 Introduction -- 2 Lower Bound -- 3 Skyline Counting Data Structure -- References -- B-slack Trees: Space Efficient B-Trees -- 1 Introduction -- 2 Related Work -- 3 B-slack trees -- 3.1 Relaxed B-slack trees -- 3.2 Updates to Relaxed B-slack trees -- 3.3 Rebalancing Steps -- 4 Analysis -- 5 Conclusion -- References -- Approximately Minwise Independence with Twisted Tabulation -- 1 Introduction -- 2 Preliminaries -- 2.1 Simple Tabulation -- 2.2 Twisted Tabulation -- 3 Minwise for Twisted Tabulation -- 3.1 Upper Bound -- 3.2 Lower Bound -- References -- Separability of Imprecise Points -- 1 Introduction
  • 2 Strong Separability -- 3 Weak Separability -- 3.1 Weak Separability by a Line -- 3.2 Weak Separability by a Rectangle -- 3.3 Approximate Weak Separability -- References -- Line-Distortion, Bandwidth and Path-Length of a Graph -- 1 Introduction and Previous Work -- 2 Preliminaries -- 3 Bandwidth of Graphs with Bounded Path-Length -- 4 Path-Length and Line-Distortion -- 5 Constant-Factor Approximation of Path-Length -- 6 Approximation of Line-Distortions of AT-Free Graphs -- References -- Colorful Bin Packing -- 1 Introduction -- 2 Algorithms -- 3 Lower Bounds -- 3.1 An Asymptotic Lower Bound of 2 -- 3.2 A Lower Bound for Zero Size Items -- References -- Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques -- 1 Introduction -- 2 Minimal Separators and Potential Maximal Clique -- 3 Relations to Vertex Cover -- 4 Relations to Modular Width -- 5 Applications -- 6 Conclusion -- References -- Win-Win Kernelization for Degree Sequence Completion Problems -- 1 Introduction -- 2 Degree Constraint Editing -- 2.1 A Polynomial Kernel for DCE(e+) with Respect to (k, r) -- 2.2 A Polynomial Kernel for DCE(e+) with Respect to r -- 3 A General Approach for Degree Sequence Completion -- 3.1 Fixed-Parameter Tractability of S-DSC -- 3.2 Applications -- 4 Conclusion -- References -- On Matchings and b-Edge Dominating Sets:A 2-Approximation Algorithm for the 3-Edge Dominating Set Problem -- 1 Introduction -- 1.1 Previous Work -- 1.2 Our Work -- 2 Preliminaries -- 3 A 2-Opt Algorithm for 2-EDS -- 4 b-Opt Matchings and Þb(G) -- 4.1 Case of 3-EDS -- 4.2 Case of b-EDS -- 5 A 3-Opt Algorithm for 3-EDS -- 5.1 Performance Analysis of 3-opt Algorithm for 3-EDS -- References -- Covering Problems in Edge- and Node-Weighted Graphs -- 1 Introduction -- 1.1 Motivation -- 1.2 Problem Definitions -- 1.3 Our Results -- 2 Related Work
  • 3 LP Relaxations -- 4 Prize-Collecting EDS Problem in Trees -- 5 Conclusion -- References -- Colored Range Searching in Linear Space -- 1 Introduction -- 1.1 Our Results -- 1.2 Previous Results -- 2 Colored Range Searching in Almost-Linear Space -- 2.1 Color Grouping and Bucketing -- 2.2 Restricted Colored Range Reporting for Buckets -- 3 2D Colored Range Searching in Linear Space -- 4 Dynamic Data Structures -- 4.1 Updating a Bucket -- 4.2 Updating Color Grouping and Point Bucketing -- 4.3 Fixing Bucket Answers during a Query -- 5 Open Problems -- References -- Fast Dynamic Graph Algorithms for Parameterized Problems -- 1 Introduction -- 1.1 Background -- 1.2 Our Contribution -- 2 Notations -- 3 Dynamic Graph for Vertex Cover -- 4 Dynamic Graph for Cluster Vertex Deletion -- 4.1 Problem Definition and Time Complexity -- 4.2 Data Structure -- 4.3 Algorithm -- References -- Extending Partial Representations of Proper and Unit Interval Graphs -- 1 Introduction -- 2 Preliminaries and Proper Interval Graphs -- 3 LP Algorithm for BoundRep with Prescribed Order -- 4 Shifting Algorithm for BoundRep with Fixed Ordering -- 4.1 Structural Properties of Unit Interval Representations -- 4.2 The Shifting Algorithm -- 5 Extending Unit Interval Representations -- References -- Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams -- 1 Introduction -- 2 Euler Diagrams -- 3 Preliminaries -- 4 Minimum Tree Supports for Labeled Hypergraphs -- 5 Minimum Tree Supports for Hypergraphs -- 6 Conclusion -- References -- Additive Spanners: A Simple Construction -- 1 Introduction -- 2 Creating a 6-Spanner -- 3 Creating a 2-Spanner -- References -- Assigning Channels via the Meet-in-the-Middle Approach -- 1 Introduction -- 2 Yet AnotherO{u2217}(( +2)n)-Time Dynamic Programming -- 3 The Meet-in-the-Middle Speed-Up -- 4 Hardness of Generalized T-Coloring
  • References -- Consistent Subset Sampling -- 1 Introduction -- 2 Preliminaries -- 3 Our Contribution -- 3.1 Time-Space Trade-Offs Revisited -- 3.2 Main Result -- 4 Our Approach -- 4.1 Intuition -- 4.2 The Hash Function -- 4.3 The Algorithm -- 5 Applications of Consistent Subset Sampling -- 6 Conclusions -- References -- Triangle Counting in Dynamic Graph Streams -- 1 Introduction -- 2 Preliminaries -- 3 The New Approach -- 3.1 The Main Idea -- 3.2 The Algorithm -- 3.3 Theoretical Analysis -- References -- Linear Time LexDFS on Cocomparability Graphs -- 1 Introduction -- 2 Background -- 3 The Algorithm -- 3.1 Vertex Labelling -- 3.2 Partition Refinement -- 3.3 The Complete Algorithm -- 4 Correctness of the Algorithm -- 5 Conclusion and Open Problems -- References -- Quantum Algorithms for Matrix Products over Semirings -- 1 Introduction -- 2 Preliminaries -- 3 Existence Dominance Matrix Multiplication -- 4 Applications: (max, min)-Product, Distance Product -- 4.1 Quantum Algorithm for the (max,min)-Product -- 4.2 Quantum Algorithm for the Distance Product -- References -- Ranked Document Selection -- 1 Introduction and Related Work -- 2 The Top-k Framework -- 3 Super-Linear Space Structure -- 3.1 The Basic Structure -- 3.2 Query Algorithm for Document Selection -- 3.3 An Enhanced Structure -- 4 Linear Space Structure -- 4.1 Encoding stab.countx(j) -- 4.2 Encoding left.ptrx(j) and right.ptrx(j) -- 4.3 Reducing Space of the Enhanced Structure -- 5 Achieving O(log k) Query Time and Better -- 5.1 Structure DS(e) -- 5.2 Structure for k {u2264} er+1 -- 5.3 Speeding Up the Enhanced Structure -- 6 Hardness of an Efficient Succinct Solution -- References -- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments -- 1 Introduction -- 2 Rounding the Hitting Set LP Using a Degree Based Vertex Ordering -- 3 Guarding Special Sets of Segments
  • 3.1 Exploiting Girth 4 in the Underlying Graph
http://library.link/vocab/cover_art
https://contentcafe2.btol.com/ContentCafe/Jacket.aspx?Return=1&Type=S&Value=9783319084046&userID=ebsco-test&password=ebsco-test
Dimensions
unknown
http://library.link/vocab/discovery_link
{'f': 'http://opac.lib.rpi.edu/record=b4383511'}
Extent
1 online resource (409 pages)
Form of item
online
Isbn
9783319084046
Media category
computer
Media MARC source
rdamedia
Media type code
c
Sound
unknown sound
Specific material designation
remote

Library Locations

    • Folsom LibraryBorrow it
      110 8th St, Troy, NY, 12180, US
      42.729766 -73.682577
Processing Feedback ...