Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Joint International Conference, FAW-AAIM 2012, Beijing, China, May 14-16, 2012, Proceedings
Published on 29. April 2012
XVII, 370 pages
978-3-642-29700-7 (ISBN)
Description
This book constitutes the refereed proceedings of the 6th International Frontiers of Algorithmics Workshop, FAW 2012, and the 8th International Conference on Algorithmic Aspects in Information and Management, AAIM 2012, jointly held in Beijing, China, in May 2012.
The 33 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 81 submissions. The papers are organized in topical sections on algorithms and data structures, algorithmic game theory and incentive analysis, biomedical imaging algorithms, communication networks and optimization, computational learning theory, knowledge discovery, and data mining, experimental algorithmic methodologies, optimization algorithms in economic and operations research, pattern recognition algorithms and trustworthy algorithms and trustworthy software.
More details
Other editions
Additional editions
Jack Snoeyink | Pinyan Lu | Kaile Su
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Joint International Conference, FAW-AAIM 2012, Beijing, China, May 14-16, 2012, Proceedings
Book
04/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Computational Geometry Approaches to Some Algorithmic Problems in Air Traffic Management
- Combinatorial Methods for Inferring Isoforms from Short Sequence Reads
- Table of Contents
- Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations
- Introduction
- Floorplans and Mosaic Floorplans
- Applications of Floorplans and Mosaic Floorplans
- Baxter Permutations
- Previous Work on Representations of Floorplans and Mosaic Floorplans
- Main Result
- Optimal Representation of Mosaic Floorplans
- Standard Form of Mosaic Floorplans
- Staircases
- Deletable Rectangles
- Optimal Binary Representation
- Conclusion
- References
- Succinct Strictly Convex Greedy Drawing of 3-Connected Plane Graphs
- Introduction
- Preliminaries
- Metric Function H(u,v)
- Greedy Drawing Property
- Strictly Convex Embedding
- References
- Weighted Inverse Minimum Cut Problem under the Sum-Type Hamming Distance
- Introduction
- Preliminary Results
- Complexity of the General Case
- A Polynomial Solvable Case
- Concluding Remarks
- References
- Voronoi Diagram with Visual Restriction
- Introduction
- Combinatorial Complexity of VRVD
- Algorithm for Computing Visual Restriction Voronoi Diagram
- Concluding Remarks
- References
- Minimization of the Maximum Distance between the Two Guards Patrolling a Polygonal Region
- Introduction
- Preliminary
- Properties of the Min-max Walks
- Algorithm
- Concluding Remarks
- References
- On Covering Points with Minimum Turns
- Introduction
- Mistakes in Previous Algorithms
- Mistakes in Previous NP-Hardness Proofs
- New NP-Hardness Proofs
- References
- On Envy-Free Pareto Efficient Pricing
- Introduction
- Model and Solution Concepts
- Unit Demand Consumers
- Pareto Efficiency and Social Welfare
- Determining Pareto Efficiency
- Complexity of Computing REP
- Single-Minded Consumers
- References
- Online Pricing for Multi-type of Items
- Introduction
- Lower Bound of the Competitive Ratio
- Online Algorithm
- References
- Algorithms with Limited Number of Preemptions for Scheduling on Parallel Machines
- Introduction
- i-Preemptive Scheduling on m Identical Machines
- i-Preemptive Scheduling on Two Uniform Machines
- Algorithm for Non-preemptive Scheduling
- Algorithm for 1-Preemptive Scheduling
- Conclusions
- References
- Computing Maximum Non-crossing Matching in Convex Bipartite Graphs
- Introduction
- Notation and Problem Statement
- Related Work
- Preliminaries
- Our Algorithm
- The Description of the Main Algorithm
- The Algorithm Implementation and the Time Analysis
- Reporting an MNCM
- References
- Algorithms for Bandwidth Consecutive Multicolorings of Graphs
- Introduction
- Preliminaries
- Exact Algorithm for Series-Parallel Graphs
- FPTAS
- Partial k-Trees
- References
- Independent Domination on Tree Convex Bipartite Graphs
- Introduction
- Intractability of IDS on Star Convex Bipartite Graphs
- Intractability of IDS on Tree Convex Bipartite Graphs
- Tractability of IDS on Tree Convex Bipartite Graphs
- Conclusion and Open Problems
- References
- On-Line Scheduling of Parallel Jobs in Heterogeneous Multiple Clusters
- Introduction
- Different Widths
- Different Speeds
- Conclusions
- References
- On Multiprocessor Temperature-Aware Scheduling Problems
- Introduction
- Notation and Preliminaries
- Makespan Minimization
- Maximum Temperature Minimization
- Average Temperature Minimization
- Weighted Average Temperature Minimization
- Conclusions
- References
- Online Minimum Makespan Scheduling with a Buffer
- Introduction
- Preliminaries
- Two Algorithms for Identical Machines
- m Machines with a Buffer of Size 3m2
- Three Machines with a Buffer of Size Six
- A Simple Algorithm for Uniform Machines
- References
- A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
- Introduction
- Models of Computation and Overview of Methods
- Overview of Our Method
- Adaptive Random Sampling for Bin Packing
- Main Results
- Streaming Approximation Scheme
- References
- Multivariate Polynomial Integration and Differentiation Are Polynomial Time Inapproximable Unless P=NP
- Introduction
- Notations
- Overview of Our Methods
- Intractability of High Dimensional Integration
- Integration of S2 Polynomial
- Inapproximation of Differentiation
- Some Tractable Integrations and Derivatives
- Bounded Width Product
- Tractable Differentiation
- References
- Some Remarks on the Incompressibility of Width-Parameterized SAT Instances
- Introduction
- Preliminary
- Incompressibility
- Incompressibility of Width Parameters
- Incompressibility of Instance Length
- Conclusion
- References
- Kernels for Packing and Covering Problems
- Introduction
- Re-cycling Kernel Results
- Crown Rules for Packing and for Covering
- Small Kernels for Tr-packing & covering Tr's
- Improving on Kernel Size: A Case Study
- Prospects
- References
- The Worst-Case Upper Bound for Exact 3-Satisfiability with the Number of Clauses as the Parameter
- Introduction
- Problem Definitions
- Estimating the Running Time
- Algorithm for Solving X3SAT
- Transformation Rules
- Helper Principle
- Algorithm X3SAT for Solving Exact 3SAT
- Conclusion
- References
- Fixed-Parameter Tractability of almost CSP Problem with Decisive Relations
- Introduction
- Preliminaries
- Parameterized Problems and Fixed-Parameter Tractability
- Constraint Satisfaction Problem
- Binary Boolean Relations
- Problem Statement and Main Result
- Graph and Separator
- Reduction by Iterative Compression
- p-MinMixedCut Is Fixed-Parameter Tractable
- Main Theorem
- Conclusions and Open Problems
- References
- On Editing Graphs into 2-Club Clusters
- Introduction
- Preliminaries
- NP-Hardness Proofs
- NP-Complteness of 2-Club Cluster Vertex Deletion
- NP-Complteness of 2-Club Cluster Editing
- Parameterized Algorithms
- An Improved Parameterized Algorithm for 2-Club Cluster Vertex Deletion
- An Improved Parameterized Algorithm for 2-Club Cluster Edge Deletion
- Conclusions
- References
- Solving Generalized Optimization Problems Subject to SMT Constraints
- Introduction
- Background
- DPLL(T) Framework
- Optimization Problem with Complex Constraints
- Solving Optimization Problems with DPLL(T)
- A Straightforward Method
- Optimization in Bunches
- Feasible Region Expansion
- The Algorithms
- Implementation and Experimental Results
- Related Works and Discussion
- Concluding Remarks
- References
- Solving Difficult SAT Problems by Using OBDDs and Greedy Clique Decomposition
- Introduction
- OBDD-Based Satisfiability Solving
- Ordered Binary Decision Diagrams(OBDDs)
- OBDD-Based Satisfiability Solving
- Greedy Clique Decomposition
- Experimental Results
- The SAT Solvers Used in Our Experiments
- Test Instances and Corresponding Clique Decomposition
- Results and Analysis
- Conclusions
- References
- Zero-Sum Flow Numbers of Regular Graphs
- Introduction to Zero-Sum Flows
- Zero-Sum Flow Numbers
- Flow Numbers for Regular Graphs
- Flow Numbers for Cartesian Products
- References
- More Efficient Parallel Integer Sorting
- Introduction
- Nonconservative Sorting
- Sorting n Integers in { 0, 1,..., 2c(logn loglogn)1/2 }
- Sorting Integers in { 0, 1, ..., n1/2 } and in {0, 1, ..., n-1}
- Conclusions
- References
- Fast Relative Lempel-Ziv Self-index for Similar Sequences
- Introduction
- Data Structure Framework
- The Relative Lempel-Ziv (RLZ) Compression Scheme
- Pattern Searching
- Some Useful Auxiliary Data Structures
- The Data Structure I(T) for Case 1
- The Data Structure X(T) for Case 2
- The Data Structure Y(F,T) for Case 2
- References
- A Comparison of Performance Measures via Online Search
- Introduction
- Problem Preliminaries
- Competitive Analysis
- Bijective Analysis
- Real-Valued Price Interval
- Average Analysis
- Random Order Analysis
- Relative Interval Analysis
- Relative Worst Order Analysis
- Concluding Remarks
- References
- Online Exploration of All Vertices in a Simple Polygon
- Introduction
- Strategy of AOE
- Competitive Analysis of AOE
- Lower Bound
- Competitive Analysis for Rectilinear Polygon
- Discussion and Open Problems
- References
- In-Place Algorithms for Computing a Largest Clique in Geometric Intersection Graphs
- Introduction
- Maximum Clique of an Interval Graph
- Maximum Clique for Arbitrary Size Rectangles
- Maximum Clique for Fixed Height Rectangles
- Processing of a Strip S
- Geometric Clique for Disks of Arbitrary Radii
- Finding Maximum Clique of the Circular-Arc Graph around Ci
- Graphical Clique in the Unit Disk Graph
- Bipartite Matching in GB
- Complexity Analysis
- References
- The Black-and-White Coloring Problem on Distance-Hereditary Graphs and Strongly Chordal Graphs
- Introduction
- Black-and-White Colorings of Cographs
- Threshold Graphs
- Difference Graphs
- Distance-Hereditary Graphs
- Interval Graphs
- Strongly Chordal Graphs
- Splitgraphs
- References
- An Improved Approximation Algorithm for the Bandpass Problem
- Introduction
- The Approximation Algorithm
- Algorithm Description
- Performance Analysis
- Conclusions and Future Work
- References
- Partial Degree Bounded Edge Packing Problem
- Introduction
- Related Work
- Maximum Expressible Independent Subset
- MEIS on 2-Regular Set
- Maximum Partial c Bounded Subgraph Problem on Tree
- Approximation Algorithms for P1B and P2B
- A 2-Approximation Algorithm for Partial 1 Bounded Subgraph
- A 32/11-Approximation Algorithm for Partial 2 Bounded Subgraph
- Conclusion
- References
- Erratum: The Approximability of the Exemplar Breakpoint Distance Problem
- Reference
- Author Index
