Frontiers in Algorithmics and Algorithmic Aspects in Information and Management

Name: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management | Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011, Proceedings

Mikhail Atallah Xiang-Yang Li Binhai Zhu(Herausgeber*in)

Springer (Verlag)

Erschienen am 30. Mai 2011

XIII, 390 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-21204-8 (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
Preface
Organization
Table of Contents
Invited Lectures
Progress in Complexity of Counting Problems
References
Recent Developments in the Theory of Pre-processing
Summary
Recent Developments in the Mechanism Design Problem for Scheduling
References
Degree-Driven Design for Correct Geometric Algorithms
Contributed Papers
Approximation Algorithm for the Uniform Bounded Facility Problem
Introduction
UBFLP Model
Greedy Approximation Algorithm for UBFLP on General Graph
Constant-Factor Approximation Algorithm for UBFLP on Plane
Conclusion
References
The k-Canadian Travelers Problem with Communication
Introduction
Problem Description
The k-Canadian Travelers Problem with Full Communication (P1)
The k-Canadian Travelers Problem with Limited Communication (P2)
Retrace-Alternating Strategy in Urban Environment
Conclusion
References
An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem
Introduction
Algorithm Description
Competitive Ratio Analysis
Proof of Lemma 1
Conclusion
References
Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs
Introduction
Preliminaries
The Complexity
AnFPTAS
Concluding Remarks
References
An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
Introduction
Preliminaries
Favorable Operations
A 73-Approximation Algorithm
The Approx-CMSR Algorithm
Performance Analysis
Conclusions
References
Greedy Routing via Embedding Graphs onto Semi-metric Spaces
Introduction
Greedy Drawing in the Euclidean Spaces
Succinctness in Greedy Drawing
Succinct-Greedy Drawing in the Hyperbolic Plane
Our Approach and Results
Greedy Routing via Embedding Graphs into Semi-metric Spaces
Greedy Routing via Semi-metric Spaces
A Group of Semi-metric Spaces
A Simple Greedy Routing Algorithm for Arbitrary Trees
Greedy Routing for Connected Graphs
References
On Variants of the Spanning Star Forest Problem
Introduction
Our Contributions
Notation Used for Approximation Algorithms
Spanning Star Forest in Graphs with Minimum Degree Constraints
Spanning k-Tree Forest Problem
Improved Approximation Algorithm
Inapproximability Results
Improved Hardness Results for Spanning Star Forest
References
An Implicit Degree Condition for Cyclability in Graphs
Introduction
The Proof of Theorem 6
References
Parallel Enumeration of Lattice Animals
Introduction
Redelmeier's Algorithm
Parallelism
Results
References
Parameterized Edge Dominating Set in Cubic Graphs
Introduction
Enumeration-Based Algorithms
Branching on Graphs of Maximum Degree 2
Some Techniques
The Algorithm
Dealing with Leaf 6-Cycles
Dealing with Leaf 7-Cycles
Dealing with (3,0) Vertices
Branching Rules in Step 7
Branching Rules in Step 8
Branching Rules in Step 9
The Finial Result
Concluding Remarks
References
On Some Geometric Problems of Color-Spanning Sets
Introduction
Computing the Maximum Diameter Color-Spanning Set
Hardness of the LCPCS Problem
NP-hardness for the Planar Minimum Color-Spanning Tree Problem
NPO-hardness for PMCST
Conclusions
References
Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere
Introduction
Preliminaries
Lower Bounds
An Efficient O(n logn) Time Approximation Algorithm
Box Cutting Phase
Carving Phase
Constant and O(logn) Factor Approximation Algorithms
A General Property
Algorithms in the Carving Phase
Concluding Remarks
References
An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs
Introduction
The Algorithm
The Complexity of the Algorithm
References
Complexity of Total {k}-Domination and Related Problems
Introduction
Preliminaries
Summary of Our Contributions
{k}-Domination and Total {k}-Domination
NP-Completeness Results
Approximation Results
Total {k}-Domatic Number
References
The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View
Introduction
Graph Model and Related Definitions
Min-power Single-source h-Multicast is in FPT
Reduction to Hop-bounded Directed Steiner Subgraph
Solving Hop-Bounded Directed Steiner Subgraph
Solving Min-power Single-source h-Multicast
Parameterized Hardness Results
Conclusions
References
Constant Sum Flows in Regular Graphs
Introduction and Preliminaries
Constant-Sum Flows for Regular Graphs
Odd Regular Graphs
Even Regular Graphs
Concluding Remarks
References
2D Knapsack: Packing Squares
Introduction
Preliminaries and Models
A Simple Algorithm IHS and Its Applications
Increasing Height Shelf
IHS Algorithm for Packing Small Items
A Modified IHS Algorithm for Packing Small Items
A Simple Polynomial Time Approximation Scheme
References
Tight Approximation Bounds for Greedy Frugal Coverage Algorithms
Introduction
The Greedy Algorithm
The Parameterized LP Lemma
The Upper Bound
Adding a Corrective Phase
The Parameterized LP Lemma
The Upper Bound
Extensions
References
Algorithms for Interval Structures with Applications
Introduction
The Single-source K-link Shortest Path Problem on Interval Graphs
Some Useful Structures of K-link Shortest Paths in I
The O(Kn) Time K-SP Algorithm
The Generalized Optimal Color-Spanning Problem
The Two-Scan G-OCS Algorithm
The One-Scan G-OCS Algorithm
References
Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time
Introduction
Problem and Algorithm
Preliminary Results
Proof of the Worst-Case Ratio
References
PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays
Introduction
Background
Notations and Suffix Array
The HiTEC Algorithm
PSAEC
Methods
Algorithm
Parallelization
Experiments
Conclusion
References
Two Hardness Results on Feedback Vertex Sets
Introduction
The Reduction
The Lower Bounds
In G(n,p)
In GRB(n,r)
Open Problems
References
Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget
Introduction
The Continuous Model
The Discrete Model
A 2-Approximation Algorithm with Energy Augmentation
Concluding Remarks
References
Plane-Filling Properties of Directed Figures
Introduction
Preliminaries
Infinite and Semi-infinite Zippers
Filling the Plane with Figures
Final Remarks
References
An Iterative Method for Generating Loop Invariants
Introduction
Preliminaries
Invariant Generation
Solving Constraints
Case Studies
Conclusion
References
Algorithms for Computing Bidirectional Best Hit r-Window Gene Clusters
Introduction
Problem Formulation
BBHRW Using Similarity Measure count
Similarity Measure count
Algorithm SWBST
Time Complexity Analysis of Algorithm SWBST
BBHRW Using Similarity Measure msint
Similarity Measure msint
Algorithm SWOT
Time Complexity Analysis of Algorithm SWOT
Results and Discussion
Experimental Setup
Comparison of the Running Time
Characteristics of BBHRW Clusters for count and msint
Conclusion
References
Contracted Webgraphs: Structure Mining and Scale-Freeness
Introduction
Contracted Webgraphs
Undirected Webgraphs
Intra-/Inter-domain Substructures and Contractions
Contracted Webgraphs
Isolated Cliques and Isolated Stars as Communities and Spams
Outline of Experiments on Contracted Webgraphs
Scale-Freeness of Contracted Webgraphs
Properties of Isolated Clique Contracted Webgraphs
Properties of Isolated Star Contracted Webgraphs
Properties of Isolated Clique and Isolated Star Contracted Webgraphs
Scale-Freeness and Self-similarities in Contracted Webgraphs
Structure Mining on Contracted Webgraphs
Structure Mining on Isolated Clique Contracted Webgraphs
Structure Mining on Isolated Star Contracted Webgraphs
Structure Mining on Isolated Clique and Isolated Star Contracted Webgraphs
Validity of Contracted Webgraphs for Structure Mining
Concluding Remarks
References
Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs
Introduction
A Simpler NP-Completeness Proof for the Edge-Disjoint Min-Min Problem in General Digraphs
Extension of the Proof to Planar Digraphs
Conclusion
References
Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing
Introduction
Preliminary
Packing Strategy
Analysis of the Strategy
References
Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints
Introduction
Deterministic Case
Randomized Case: Full Heat
Randomized Case: Non-full Heat
Multiple Processors
Conclusion
References
Temperature Aware Online Algorithms for Scheduling Equal Length Jobs
Introduction
The Nonpreemptive Model
Lower Bound
Upper Bound: Coolest First
Upper Bound: Any Reasonable Algorithm
The Preemptive Restart Model
The Preemptive Resume Model
References
Visibility Testing and Counting
Introduction
The Visibility Testing Problem
The Visibility Counting Problem
Conclusion
References
The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders
Introduction
Preliminaries
Distance Problems
Rank Aggregation Problem
Approximation Algorithms
Conclusion and Open Problems
References
Minimum Width Rectangular Annulus
Introduction
Problem Definition and Notations
Axis-Parallel Annulus
Arbitrarily Oriented Annulus
Algorithm and Complexity
Conclusion
References
An Experimental Study on Generating Planar Graphs
Introduction
Graph Generators
(n)-generators
(n,m)-generators
Summary
Experiments
Dataset Generation
Basic Graph Properties
Algorithmical Behavior
Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken