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 2012, Beijing, China, May 14-16, 2012, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

Joint International Conference, FAW-AAIM 2012, Beijing, China, May 14-16, 2012, Proceedings

Jack Snoeyink Pinyan Lu Kaile Su Lusheng Wang(Herausgeber*in)

Springer (Verlag)

Erschienen am 29. April 2012

XVII, 370 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-29700-7 (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
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

Systemvoraussetzungen

Als PDF speichern Als Link merken