Combinatorial Optimization and Applications: 5th International Conference, COCOA 2011, Zhangjiajie, China, August 4-6, 2011, Proceedings

✍ Scribed by Weifan Wang (editor), Xuding Zhu (editor), Ding-Zhu Du (editor)

• Publisher: Springer
• Year: 2011
• Tongue: English
• Leaves: 573
• Series: Lecture Notes in Computer Science; 6831
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 5th International Conference on Combinatorial Optimization and Applications, COCOA 2011, held in Zhangjiajie, China, in August 2011. The 43 revised full papers were carefully reviewed and selected from 65 submissions. The papers cover a broad range of topics in combinatorial optimization and applications focussing on experimental and applied research of general algorithmic interest and research motivated by real-world problems.

✦ Table of Contents

Title
Preface
Organization
Table of Contents
The Complexity of Testing Monomials in Multivariate Polynomials
Introduction
Notations and Definitions
Polynomials
Polynomials
2 Polynomials
2 Polynomials vs. 2 and Polynomials
Testing c-Monomials
Parameterized Algorithms
References
Algorithms for Testing Monomials in Multivariate Polynomials
Introduction
Overview
Contributions and Methods
Preliminaries
Notations and Definitions
The Group Algebra F[Zpk]
Randomized Testing of p-Monomials
Derandomization
m2t k3 Polynomials
W[1]-Hardness
References
Hybrid Artificial Bee Colony Search Algorithm Based on Disruptive Selection for Examination Timetabling Problems
Introduction
Problem Description and Formulation
Problem I
Problem II
Artificial Bee Colony Algorithm (ABC)
Basic Artificial Bee Colony (ABC) Algorithm
Onlooker Bees Selection Process
Disruptive Selection Strategy
The Proposed Algorithm
Neighborhood Search Operations
Self-adaptive Method for Neighbouring Search
A Local Search Algorithm (Simulated Annealing)
Constructive Heuristic
Improvement Algorithm
Simulation Results
Problem I
Problem II
Conclusion and Future Work
References
Heuristics for Parallel Machine Scheduling with Deterioration Effect
Introduction
Problem Statement and Notations
Heuristic LIST
Heuristic LDR
References
A Comprehensive Study of an Online Packet Scheduling Algorithm
Model Description
Algorithm MG
Analysis
The General Setting
The Agreeable Deadline Setting
The Anti-agreeable Deadline Setting
The Agreeable Value Setting
The Anti-agreeable Value Setting
The Agreeable Deadline/Value Setting
The Anti-Agreeable Deadline/Value Setting
The Agreeable Slack-Time/Value Setting
The Anti-Agreeable Slack-Time/Value Setting
References
Optimal Policy for Single-Machine Scheduling with Deterioration Effects, Learning Effects, Setup Times, and Availability Constraints
Introduction
Problem Definition and Notations
Optimality of SPT
Conclusion
References
Algebraic Algorithm for Scheduling Data Retrieval in Multi-channel Wireless Data Broadcast Environments
Introduction
Previous Works
Methodology
Problem Description
Algorithm
Conclusions
References
Hamiltonian Cycles through Prescribed Edges in k-Ary n-Cubes
Introduction
Basic Definitions and Results
The Main Result
Conclusions
References
A Fast Parallel Algorithm for Finding a Most Reliable Source on a General Ring-Tree Graph with Unreliable Edges
Introduction
Definitions and Notations
Fundamental Preliminaries
The Parallel Algorithm
An MRS on a Ring
Dynamic Programming Algorithm
Parallel Algorithm
Concluding Remarks
References
Restricted Edge Connectivity of Harary Graphs
Introduction
Preliminaries
Harary Graph of the First Type
Harary Graphs of the Second or the Third Type
Concluding Remark
References
Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem
Introduction
Basic Concepts and Preliminary Results
An Explicit Enumeration Algorithm for Finding the k Most Vital Edges
An Implicit Enumeration Algorithm for Finding the k Most Vital Edges
Lower Bounds
Upper Bound
Branching Strategy
A Mixed Integer Programming Formulation for Finding the k Most Vital Edges
Computational Results
-Approximate Algorithm
Conclusions
References
Euclidean Chains and Their Shortcuts
Introduction
Preliminaries
Properties
Simple Shortcuts
Node-0 Shortcuts
Node-1 Shortcuts
Shortcut Ratio
Algorithms
Concluding Remarks
References
List Dynamic Coloring of Sparse Graphs
Introduction
List Dynamic Coloring of Sparse Graphs
List Dynamic Chromatic Number of Planar Graphs
References
Further Improvement on Maximum Independent Set in Degree-4 Graphs
Introduction
NotationSystem
Reduction Rules
Branching Rules
The Algorithm for MIS4
TheAnalysis
Preliminaries
Step 5
Step 6
Step 7
Step 8
Step 9
Step 10
Putting All Together
Concluding Remarks
References
Approximation Algorithms for Minimum Energy Multicast Routing with Reception Cost in Wireless Sensor Networks
Introduction
Related Work
Network Model and Problem Specification
Algorithms for the MEM-R Problem
Fixed Power Level
l(v) Power Levels
Conclusion
References
Public Communication Based on Russian Cards Protocol: A Case Study
Introduction
An Improved Russian Cards Protocol
Correction of the Algorithm
Improvement of the Algorithm
A Case Study
Related Works
Conclusion
References
Minimum Latency Data Aggregation in Wireless Sensor Network with Directional Antenna
Introduction
Related Work
Network Model and Directional Antenna Model
Directional Antenna Model
Network Model
Problem Definition
Algorithm
Constructing Initial Data Aggregation Tree
Scheduling for the Directional Data Aggregation
Performance Analysis
Time Complexity
Algorithm Approximation Ratio
References
A Near-Optimal Memoryless Online Algorithm for FIFO Buffering Two Packet Classes
Introduction
Algorithm
The Idea
A Memoryless Online Algorithm for the Two-Valued Model
Analysis
Related Work and Open Problems
References
On the Maximum Locally Clustered Subgraph and Some Related Problems
Introduction
Preliminaries
Notations and Definitions
Problem Modeling
The MCNE Problem
The MLCS Problem
The NP-Hardness
Polynomial Time Solvable Cases
Algorithms for Graphs with Non-overlapped Maximal Cliques
Conclusion
References
Quickest Paths in Anisotropic Media
Introduction
Problem Formulation
Previous Work
Our Contribution
An Efficient (1+) Approximation Algorithm
Placing Steiner Points
Constructing the Graph
Bounding the Error of the Approximation
Shortest Path Queries
The Preprocessing and the Query
Approximation Bound
General Case
Concluding Remarks
References
Mechanisms for Obnoxious Facility Game on a Path
Introduction
Preliminaries
Deterministic Mechanisms
Randomized Mechanisms
Concluding Remarks
References
Algorithmic Aspects of Heterogeneous Biological Networks Comparison
Introduction
Preliminaries
Partition Version of k-DAGCC
Cover Version of k-DAGCC
Conclusion
References
Minimum Interval Cover and Its Application to Genome Sequencing
Introduction
A Greedy Approximation Algorithm for the c-Interval Cover Problem
Complexity of the c-Interval Cover Problem
Experimental Results
Implementation Details
Results
Conclusion
References
Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem
Introduction
An O(2nnO(1)) Time Algorithm for General Cases
Polynomial Time Algorithm for Almost All Cases
Algorithms for the Lower Bound of MCSP
Concluding Remarks
References
Complexity of the Stamp Folding Problem
Introduction
Preliminaries
NP-Completeness
Tractability for Bounded k
Concluding Remarks
References
On the Number of Solutions of the Discretizable Molecular Distance Geometry Problem
Introduction
The Formal Definition of the Discretizable Molecular Distance Geometry Problem
Sphere Intersections and Reflections
Branch-and-Prune
Geometry in BP Trees
Symmetry and Number of Solutions
Counterexamples
Disproving the ``Power of Two'' Conjecture
Necessity of Immediate Predecessors
Conclusion
References
Integration of an LP Solver into Interval Constraint Propagation
Introduction
Integration of an LP Solver into iSAT
Introducing iSAT
Integration of an LP Solver
Solving the Linear Programs and Computation of Small Infeasible Subsets
Experiments
Comparison of Different LP Solving Techniques
Detailed Evaluation of Our Certifying Approach
Summary
Conclusion
References
A Saturation Algorithm for Homogeneous Binomial Ideals
Introduction
Problem Description
Related Work in Literature
Our Approach
Refined Problem Statement
Chain and Chain-Binomial
Decomposition into Chains
Reduction of U-Binomials
Pseudo-Gröbner Basis
Saturation with Respect to xi
Final Algorithm
Preliminary Experimental Results
References
Improved Algorithms for Farthest Colored Voronoi Diagram of Segments
Introduction
Farthest Colored Voronoi Diagram of Segments
Farthest-Polygon Voronoi Diagram
Conclusion
References
One-and-a-Half-Side Boundary Labeling
Introduction
Preliminaries
The Models for 1.5-Side Boundary Labeling
Problem Setting
Uniform-Label Cases
Nonuniform-Label Cases
NP-Hardness
Pseudo-polynomial Time Algorithm
Fixed-Parameter Algorithm
Conclusion
References
Approximation Algorithms for a Bi-level Knapsack Problem
Introduction
Preliminary and Problem Formulation
The Competitive Version
Algorithm Algc
Analysis of the Algorithm
A Lower Bound
The Beneficial Version with W1>W2
Algorithm Algm1
Analysis of the Algorithm
A Lower Bound
The Beneficial Version with W1W2
A Subproblem and the Corresponding Algorithm
Algorithm Algm2
Analysis of the Algorithm
A Lower Bound
Conclusions
References
On the Surface Area of the Asymmetric Twisted Cube
Introduction
Twisted Cube and Its Routing
A General Surface Area Result for the Twisted Cube
Surface Areas at Specific Centers for the Twisted Cube
Comparison of the Twisted Cube and Other Variants
Concluding Remarks
References
Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
Introduction
Definitions
The Algorithm
The Analysis
Open Problem
References
On the Partition of 3-Colorable Graphs
Introduction
Preliminaries
Parameterized Algorithm
Two Properties When G[V-SB-SI] Is a Union of Disjoint Paths/Cycles
Main Algorithm
Future Work
References
Kinetic Red-Blue Minimum Separating Circle
Introduction
Preliminaries
General Approach
The Minimum Separating Circle with One Mobile Blue Point
The Minimum Separating Circle with One Mobile Red Point
The Minimum Separating Circle with Multiple Moving Points
References
A Semantic Model for Many-Core Parallel Computing
Introduction
Preliminaries
Projection Temporal Logic
Modeling, Simulation and Verification Language
Cylinder Computation Model
Operational Semantics of CCM
Implementation of CCM in MSVL Interpreter
Case Study: A Word Processor
Related Work
Conclusions
References
On Unique Games with NegativeWeights
Introduction
Preliminaries
GUGP-NWA
GUGP-PWT()
Parallel Repetition of Max 3-Cut
Unique Game Conjecture on GUGP-PWT()
Discussions
References
A Note on Treewidth in Random Graphs
Introduction
Preliminaries
The Upper Bound
The Lower Bound
Application
Open Problems
References
On the Two-Stage Stochastic Graph Partitioning Problem
Introduction
The Model of the Two-Stage Stochastic Graph Partitioning Problem
Equivalent Integer Linear Programming Formulations
Experimental Results
Conclusions
References
A Spatio-Temporal Approach to the Discovery of Online Social Trends
Introduction
Online Social Networks Data Collection
Design of OSN Data Collection Engines
The Spatio-Temporal Database System
Database Design
Access Methods
Query Platform
Predicting Flu Trends Using Twitter Data: A Case Study
Data Sets
Twitter Improves Prediction of Influenza Data
Summary
References
A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design
Introduction
Preliminaries
LP Formulation
Algorithm
A Simple Greedy Algorithm
A Bicriteria LP-Rounding Algorithm
An O(q)-Approximation Algorithm
References
Greedy Algorithm for Least Privilege in RBAC Model
Introduction
Least Privilege User-Role Assignment Problem
Problem Formulation
Minimum Submodular Cover with Submodular Cost
Greedy Algorithm
Parameter Definition
Algorithm
Results
Performance Analysis
Conclusion
References
Towards Minimum Delay Broadcasting and Multicasting in Multihop Wireless Networks
Introduction
Related Work
Broadcasting and Multicasting with Single Source
Network-Wide Broadcasting
Multicasting
Multicasting with Multiple Sources
Offline Algorithm
Online Algorithm
Simulation
Broadcasting and Multicasting with a Single Source
Multicasting with Multiple Sources
Conclusion
References
Author Index