Combinatorial Optimization and Applications

Name: Combinatorial Optimization and Applications | 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings

Zaixin Lu Donghyun Kim Weili Wu Wei Li Ding-Zhu Du(Herausgeber*in)

Springer (Verlag)

Erschienen am 8. Dezember 2015

XIII, 810 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-26626-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

Intro
Preface
Organization
Contents
Classic Combinatorial Optimization
Improved Algorithms for the Evacuation Route Planning Problem
1 Introduction
2 Related Work
3 Problem Definition and Model
4 The Single Source Single Sink Problem
4.1 Limitation of QPER Algorithm for SSEP
4.2 Modified Algorithm for SSEP When We Are Given k Edge-Disjoint Paths
4.3 An Important Observation
4.4 Our Algorithm for SSEP
4.5 Running Time Analysis of SSEP
4.6 CCRP Algorithm for SSEP and Some Observations
4.7 Analysis of Algorithm [1]
5 Randomized Behavior Model of People
5.1 Lower Bound for Expected Evacuation Time
5.2 Algorithm for Randomized Behavior of People
6 Experimental Results
6.1 Details of the Experiments
6.2 Results
7 Conclusion and Future Work
References
Improved MaxSAT Algorithms for Instances of Degree 3
1 Introduction
2 Reduction Rules
3 An O*(1.194k)-time Parameterized Algorithm
4 An O*(1.237n)-time Algorithm for (n,3)-MaxSAT
5 Conclusion
References
Directed Pathwidth and Palletizers
1 Introduction
2 Preliminaries
3 Main Result
4 Applications
4.1 Hardness Result
4.2 Bounded FIFO Stack-Up Systems
4.3 Approximation
5 Conclusion
References
Black and White Bin Packing Revisited
1 Introduction
2 Algorithm ``Balance Between Stacks''
2.1 Description of Algorithm BAL
3 Competitive Analysis of Algorithm BAL
3.1 Terminology and Case Analysis
3.2 A Function Calculating the Total Size of Bins
3.3 Case by Case Analysis of the Competitive Ratio of BAL
4 Concluding Remarks
References
Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties
1 Introduction
2 General Local Search Algorithm
3 Local Search for k-MPLP
3.1 Analysis
4 Local Search for k-FLPLP
4.1 Analysis
4.2 Improve the Local Gap Using Scaling Technique
5 Polynomial-Time Algorithm for k-MPLP and k-FLPLP
References
A (5.83+)-Approximation Algorithm for Universal Facility Location Problem with Linear Penalties
1 Introduction
2 Local Search Algorithm
2.1 Operations
2.2 Polynomial-Time Proof
2.3 Algorithm
3 Analysis
4 Discussions
References
Variants of Multi-resource Scheduling Problems with Equal Processing Times
1 Introduction
2 Literature Review, Framework and Notations
2.1 Related Work
2.2 Objective Functions
2.3 Network Flows
2.4 Scheduling Graph
3 Variety of Machines
4 General Objective Function
5 Monotonic Objective Function
6 Periodic Objective Function
6.1 Scheduling Problem as a Network Flow
6.2 Periodic Objective Function Formulated as a Network Flow
7 Additional Remark
8 Conclusion
References
Geometric Optimization
The Discrete and Mixed Minimax 2-Center Problem
1 Introduction
2 The Discrete Minimax 2-Center Problem
3 The Mixed Minimax 2-Center Problem
3.1 The Structure of the Optimal Solution
3.2 Solving MMM2CP for a Fixed p and r
3.3 The Monotone Property
4 Conclusion
References
Approximation Algorithms for Generalized MST and TSP in Grid Clusters
1 Introduction
2 The GGMST Approximation Algorithm
3 The Lower Bound Proof
4 Approximation of the GGTSP
5 Conclusions
References
Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line
1 Introduction
2 Set Cover and Hitting Set Problems
2.1 Unit Squares Intersecting a Diagonal Line
2.2 Unit-Height Rectangles Intersecting a Diagonal Line
2.3 Unit Squares Touching a Diagonal Line
3 Piercing Set Problem
3.1 Rectangles Intersecting a Diagonal Line
3.2 Unit Squares Intersecting a Diagonal Line
4 Independent Set Problem
4.1 Squares Intersecting a Diagonal Line
4.2 Unit-Height Rectangles Intersecting a Diagonal Line
References
Optimal Self-assembly of Finite Shapes at Temperature 1 in 3D
1 Introduction
2 Definitions
2.1 3D Abstract Tile Assembly Model
2.2 Complexities of (Scaled) Finite Shapes
3 Main Theorem
4 Main Construction
4.1 Setup
4.2 Seed Block
4.3 Growth Blocks
4.4 Putting It All Together
5 Conclusion
References
Line Segment Covering of Cells in Arrangements
1 Introduction
2 NP-hardness for Rectilinear Line Segments
2.1 Reduction
2.2 Correctness
3 Covering Only Rectangular Cells
3.1 NP-hardness
3.2 FPT on the Size of the Optimal Solution
4 Rectangular Subdivisions
5 Conclusions and Open Problems
References
An Improved On-line Strategy for Exploring Unknown Polygons
1 Introduction
2 Preliminaries
2.1 An Overview of the 2-approximation Algorithm
2.2 An Overview of the 26.5-Competitive Strategy
3 Exploring a Right Polygon
3.1 How to Reach the Cut of a Right Vertex at the Wanted Point
3.2 The Exploration Strategy
3.3 The Performance Analysis
4 Exploring a Simple Polygon
4.1 The 6.7-Competitive Strategy
References
Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
1 Introduction
2 Problem Statement
3 Iterated Tour Partition Heuristic
4 Approximation of TSP in R3
5 Polynomial Time Approximation Scheme for Capacitated Vehicle Routing Problem in 3-Dimensional Space
6 Conclusion
References
Network Optimization
A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
1 Introduction
2 The Model, the Context, and Our Results
2.1 Related Work
2.2 Our Results
3 The TSS Algorithm
4 Estimating the Size of the Solution
5 Proofs of Optimality
6 Computational Experiments
6.1 Random Graphs
6.2 Large Real-Life Networks
7 Concluding Remarks
References
An Efficient Shortest-Path Routing Algorithm in the Data Centre Network DPillar
1 Introduction
2 The DCN DPillar
3 Abstracting Routing in DPillar
3.1 Another Abstraction: The Marked Cycle
4 Routing in a Marked Cycle
4.1 A Shortest Path has at Most Two Turns
5 An Optimal Routing Algorithm for DPillar
5.1 Building Our Set of Paths When x =0
5.2 Building Our Set of Paths When x = 0
5.3 Our Algorithm
6 Conclusions
References
A Sensor Deployment Strategy in Bus-Based Hybrid Ad-Hoc Networks
1 Introduction
2 Related Work
3 Network Model
4 Problem Definition and Assumptions
5 Sensor Deployment Scheme
5.1 Simple Large Regions Without Boundaries
5.2 Large Regions with Boundaries
6 Simulations
6.1 Simulation Scenarios
6.2 Simulation Analysis for Sensor Deployment
6.3 Simulation Analysis for Average Delay
7 Conclusion and Future Works
References
New Insight into 2-Community Structures in Graphs with Applications in Social Networks
1 Introduction
2 Preliminaries
3 2-Community Structure in 3-Regular Graphs
4 Balanced 2-Community Structure
5 Conclusion and Open Problems
References
WDCS: A Weight-Based Distributed Coordinate System
1 Introduction
2 Problem Formulation
3 WDCS: A High-Precision Scheme
3.1 Overview Of WDCS
3.2 Details of WDCS
4 Experimental Results
4.1 Evaluation Metrics
4.2 Accuracy
4.3 Convergence Behaviour
5 Conclusion
References
Adaptive Scheduling Over a Wireless Channel Under Constrained Jamming
1 Introduction
2 Model
3 Uniform Packets
4 Optimal Algorithm for f= 1
5 Optimal Algorithm for ANY f& 1
6 Discussion
References
Metric and Distributed On-Line Algorithm for Minimizing Routing Interference in Wireless Sensor Networks
1 Introduction
2 Related Works
3 Interference Metric
3.1 Network Model
3.2 Quantifying Interference Level
3.3 Analysis of Interference Metric
4 Distributed On-Line Algorithm
4.1 Description of DOAMI
5 Simulation Results
6 Conclusion
References
Distributed Algorithm for Mending Barrier Gaps via Sensor Rotation in Wireless Sensor Networks
1 Introduction and Related Works
2 Network Model and Problem Definition
3 Distributed Algorithm for Weak Barrier Coverage
3.1 Phase 1: Neighbor Discovery
3.2 Phase 2: Optimal Orientation
3.3 Phase 3: Minimizing the Gap Length
4 Simulation Results
5 Conclusions
References
Applied Optimization
A Hybrid Large Neighborhood Search for Dynamic Vehicle Routing Problem with Time Deadline
1 Introduction
2 Problem Formulation
3 Hybrid Large Neighborhood Search
3.1 Insert Heuristic
3.2 Large Neighborhood Search
4 Computational Results
4.1 Static Results and Analysis
4.2 Dynamic Results and Analysis
5 Conclusion
References
Indoor Localization via Candidate Fingerprints and Genetic Algorithm
1 Introduction
2 Related Work
3 Problem Formulation
4 Pick the CFs
5 Search Closest Fingerprint Using GA
5.1 Example Scenario
5.2 The Genetic Algorithm
6 Performance Evaluation
6.1 Analytical Model for Selecting CFs
6.2 The Effect of CFs Selecting
6.3 The Effect of Communication Distance
6.4 Localization Errors
7 Conclusion
References
On Clustering Without Replication in Combinatorial Circuits
1 Introduction
2 Graph Preliminaries
3 Statement of Problems
4 Related Work
5 Computational Complexity of CN
6 A 2-Approximation Algorithm for CN"426830A N, 2, "526930B
7 Conclusion
References
On Replica Placement in High-Availability Storage Under Correlated Failure
1 Introduction
2 Model
3 An O(n2) Greedy Algorithm
4 Balanced Placements
5 An O(n + log) Algorithm
5.1 Divide Phase
5.2 Combine Phase
5.3 Transform Phase
6 Conclusion and Future Work
References
Observing the State of a Smart Grid Using Bilevel Programming
1 Introduction
2 Problem Statement
2.1 Observability of a Graph
3 Mathematical Modelling
3.1 Iterative Model
3.2 From Iterative to Bilevel Model
3.3 Bilevel Model
4 An Algorithm for the Bilevel Problem
5 Computational Results
6 Conclusions
References
Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection
1 Introduction
1.1 Our Contribution
2 Related Work
3 Model and Problem Definition
4 Results
4.1 On Maximizing Immediate Gain
4.2 Lower Bound on Optimal Cost
4.3 Deterministic (3+(c-1)/c)-Approximation Schedule
4.4 On Optimal Memoryless Schedule
4.5 On Adaptive Algorithm for Memoryless Schedules
References
Complexity and Game
Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
1 Introduction
1.1 Database Application
1.2 Literature Review of the Vertex Cover Problem
1.3 Our Contribution
2 Complexity and Inapproximation
3 A Near Optimal ( 2-12r)-approximation
3.1 A Basic Approximation Algorithm
3.2 Improve the Approximation by Triangle Eliminating
3.3 Near Optimality
References
On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs
1 Introduction
2 Notation and Problem Description
3 Dense Graphs
3.1 Good News
3.2 Bad News
4 Sparse Graphs
4.1 Bad News
4.2 Good News
5 Conclusion
References
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
1 Introduction
2 Preliminaries and Basic Tools
2.1 Basic Tools
3 T-free Edge Deletion
3.1 Base Cases
3.2 Induction
4 R-free Edge Deletion
5 Handling Disconnected Graphs
6 Concluding Remarks
References
Multicast Network Design Game on a Ring
1 Introduction
2 Preliminaries
3 Price of Anarchy/Stability for Multicast on Rings
4 Potential-Optimum Price of Anarchy for Multicast on Rings
5 Myopic Sequential Prices of Anarchy/Stability
5.1 Sequential Price of Anarchy in Multicast Game on Rings
5.2 Myopic Sequential Price of Stability in Multicast Game
5.3 Myopic Sequential Price of Stability on Rings
6 Conclusions
A Weights for Inequalities from the Proof of Theorem??
References
Extreme Witnesses and Their Applications
1 Introduction
2 Preliminaries
3 Extreme Witnesses for Boolean Convolution
3.1 String Matching
3.2 (min, +) Convolution
4 Extreme Witnesses for Boolean Matrix Product
4.1 Lightest Triangles
5 Final Remarks
References
Orbital Independence in Symmetric Mathematical Programs
1 Introduction
2 Previous Work and Notation
2.1 Mathematical Programming
2.2 Symmetry Detection
2.3 Formulation and Solution Groups
2.4 Symmetry Breaking Constraints
2.5 Orbits
2.6 Strong and Weak SBCs
2.7 Stabilizers
3 Orbital Independence Notions
3.1 Incompatible SBCs
3.2 Some Existing OI Conditions
3.3 New Conditions for OI
3.4 SBCs from Independent Sets
4 Orbital Independence Algorithm
4.1 Independence Graph
4.2 Orbital Independence Reformulations
4.3 Algorithm Description
5 Computational Experiments
5.1 Environment
5.2 Results
6 Conclusions
References
Symbolic Model Checking for Alternating Projection Temporal Logic
1 Introduction
2 Alternating Projection Temporal Logic
2.1 APTL Syntax
2.2 APTL Semantics
2.3 Normal Form of APTL
3 Interpreted Systems and Symbolization
3.1 Interpreted Systems
3.2 Symbolic Representation of System Models
4 Symbolic Model Checking for APTL
4.1 Symbolic Model Checking Algorithm for APTL
4.2 Model Checker MCMAS_APTL
4.3 A Case Study
5 Conclusions
References
Optimization in Graphs
An I/O Efficient Algorithm for Minimum Spanning Trees
1 Introduction
2 The Stages
3 A Phase
4 A Proof of Correctness
5 The I/O Complexity
References
The Connected p-Centdian Problem on Block Graphs
1 Introduction
2 Problem Formulation
3 The CpM Problem on Block Graph with Unit Edge Length
4 The Connected p-Centdian Problem on Unweighted Block Graphs
5 An Example for the Connected p-Centdian Problem
References
Searching for (near) Optimal Codes
1 Introduction
2 Preliminaries
3 New Binary Linear Codes Searching from Circulant Graphs
4 New Additive Codes Searching from Circulant Graphs
5 Concluding Remarks
References
Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs
1 Introduction
1.1 Previous Work
1.2 Our Results
2 Ding and Lin's Local Search Algorithm
2.1 Preliminaries
2.2 Local Search Algorithm
3 Weight Increase in Weighted ER Random Graphs
3.1 ER and Weighted ER Random Graphs
3.2 Fundamental Lemmas
3.3 Expected Update Time in Weighted ER Random Graphs
4 Edge Deletion in ER Random Graphs
5 Concluding Remarks
References
Trees, Paths, Stars, Caterpillars and Spiders
1 Introduction
2 Linear Arboricity of Bipartite Graphs
2.1 K2k-1,2k and Tc
2.2 Linear Arboricity 2
2.3 Linear Arboricity k for k 3
3 Star Arboricity of Bipartite Graphs
4 Caterpillar Arboricity of Bipartite Graphs
5 Spider Arboricity of Bipartite Graphs
6 Concluding Remarks
References
Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset
1 Introduction
2 Definitions
3 An Algorithm for DalkS Based on the Minimum s-t Cut with at Least k Vertices
4 A Greedy Approximation Algorithm for DSS
5 Conclusion
References
Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
1 Introduction
1.1 Review of Previous Work
1.2 Notation and Problem Definition
1.3 Tree Decompositions
2 Treewidth of Real Networks
3 The Algorithm
3.1 The Signature of a Node
3.2 Running Time and Extensions
4 Conclusions and Open Problems
References
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
1 Introduction
2 Problems and Previous Results
2.1 Definitions
2.2 Optimal Approximation Algorithm for Max d-Club with Even d in [3]
3 Optimal Approximation Algorithm for Max d-Club with Odd d
4 Polynomial-Time Algorithms of Max d-Club for Graph Classes
4.1 Graph Classes
4.2 Algorithms
4.3 Chordal and Weakly Chordal Graphs for Odd d
4.4 Strongly Chordal, Trapezoid, and Interval Graphs
5 Max d-Clique
References
The Influence of Preprocessing on Steiner Tree Approximations
1 Introduction
2 Approximation Algorithms and Their Engineering
3 Preprocessing Techniques
4 Experimental Evaluation
5 Conclusion
A Distribution of Solution Values
B More Detailed Table for Influence of Preprocessing
References
Legally (+2)-Coloring Bipartite Outerplanar Graphs in Cubic Time
1 Introduction
2 Bipartite Outerplanar Graphs with =3
3 Bipartite Outerplanar Graphs with 4
3.1 Ordered Breadth First Search
3.2 A Legal (+2)-coloring Algorithm
References
Maximum Independent Set on B1-VPG Graphs
1 Introduction
2 Preliminaries
3 Approximation for B1-VPG
4 Analysis of IndSet1 and IndSet2
4.1 Analysis of Running Time
5 Approximation for Equilateral B1-VPG:
6 Hardness of MIS on Unit L-Graphs
7 Conclusion and Remarks
References
Approximating the Restricted 1-Center in Graphs
1 Introduction
2 Problem Definitions and Intractability
3 An FPTAS for RV1CP
4 Approximation Algorithms for RA1CP
4.1 Fundamental Properties
4.2 Approximation Algorithms
5 Concluding Remarks
References
The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs
1 Introduction
2 Preliminaries
3 The Disjunctive Bondage Number of Graphs
3.1 Some Exact Values
3.2 Some Upper Bounds
4 The Disjunctive Total Bondage Number of Some Graphs
5 Closing Remark
References
Edge-Disjoint Packing of Stars and Cycles
1 Introduction
2 Hardness Results
3 Kernelization Results
3.1 Kernelization for Edge-Disjoint k-Packing of s-Stars
3.2 Kernelization for Edge-Disjoint k-Packing of 4-Cycles
References
Dynamic Minimum Bichromatic Separating Circle
1 Introduction
1.1 Related Work
1.2 Our Results
2 A Unified Approach for Insertion/Deletion of Blue Points
3 Logarithmic Query for Insertions
4 Conclusions and Future Work
References
Miscellaneous
Searching Graph Communities by Modularity Maximization via Convex Optimization
1 Introduction
2 Preliminaries
3 Problem Definition
3.1 The Convex Optimization Problem
3.2 CAR - Convex Optimization Based Accurate Rounding Algorithm
4 Conclusion
References
A New Tractable Case of the QAP with a Robinson Matrix
1 Introduction
2 Conic Representation of Specially Structured Matrices
2.1 Cut Weights and Specially Structured Matrices
2.2 Recognizing Conic Combinations of Cut Matrices in CDW Normal Form
3 Conclusions
References
An Online Model of Berth and Quay Crane Integrated Allocation in Container Terminals
1 Introduction
1.1 Related Work
2 Problem Description and Basic Notations
3 The Online Algorithm and Its Basic Properties
3.1 Algorithm Description
3.2 Basic Properties
4 Competitive Analysis of Algorithm GLR
5 A Matching Lower Bound
6 Conclusion
References
On the Minimal Constraint Satisfaction Problem: Complexity and Generation
1 Introduction
2 The Minimal CSP: Definitions and Complexity
2.1 Definitions
2.2 Complexity
3 Generating Minimal CSP Instances
3.1 Preliminary Notions
3.2 The Generator
3.3 Behavior of the Minimal CSP
4 Conclusion
References
Algebraic Theory on Shortest Paths for All Flows
1 Introduction
2 Single Source Shortest Path Problem
3 Single Source Bottleneck Path Problem
4 Single Source Shortest Paths for All Flows
5 A Faster Algorithm for SSSP-AF
6 Single Source Bottleneck Paths for All Costs Problem (SSBP-AC)
7 Concluding Remarks
References
The Minimum Acceptable Violation Ranking of Alternatives from Voters' Ordinal Rankings
1 Introduction
2 Formulation
2.1 Preliminaries
2.2 Minimum Acceptable Violation Ranking Model
3 Ranking Procedure
3.1 Branch-and-Bound Ranking Procedure
3.2 A Numerical Example
4 Numerical Experiments
5 Conclusions
References
Listing Center Strings Under the Edit Distance Metric
1 Introduction
2 Related Work
3 Preliminaries
3.1 Edit Distance
4 Listing Center Strings
4.1 Algorithm ListBall: Listing Strings within Distance d
4.2 Listing Center Strings
5 Listing Common Subsequences
6 Concluding Remarks
References
Online Scheduling for Electricity Cost in Smart Grid
1 Introduction
2 Preliminaries
3 Algorithm and Competitive Analysis
4 Conclusions and Remarks
References
Proportional Cost Buyback Problem with Weight Bounds
1 Introduction
2 Preliminaries
3 The Matroid Constraint
3.1 An Optimal Online Algorithm
3.2 Lower Bound
4 The Unweighted Knapsack Constraint
4.1 Optimal Online Algorithms
4.2 Lower Bound for the Knapsack Constraint Case
References
Author Index
Erratum to: On Replica Placement in High-Availability Storage Under Correlated Failure
Erratum to: Chapter 26: Z. Lu et al. (Eds.) Combinatorial Optimization and Applications DOI: 10.1007/978-3-319-26626-8_26

Systemvoraussetzungen

Als PDF speichern Als Link merken