Combinatorial Optimization and Applications

Name: Combinatorial Optimization and Applications | 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I

Xiaofeng Gao Hongwei Du Meng Han(Editor)

Springer (Publisher)

Published on 6. December 2017

XVIII, 483 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-71150-8 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
Organization
Contents -- Part I
Contents -- Part II
Network
Filtering Undesirable Flows in Networks
1 Introduction
1.1 Related Work
2 Model
2.1 Local Ratio Approximation
3 Hardness
4 Approximation
5 Conclusion
References
A Framework for Overall Storage Overflow Problem to Maximize the Lifetime in WSNs
1 Introduction
2 Related Work
3 Overall Storage Overflow Problem
4 Data Aggregation for Overall Storage Overflow Problem
4.1 Data Aggregation Formulation
4.2 Data Aggregation Algorithm
5 Integrating Data Aggregation and Data Redistribution
6 Performance Evaluation
6.1 Performance of Data Aggregation Algorithm
6.2 Performance of Data Replication Algorithm
7 Conclusions and Future Work
References
Floorplans with Columns
1 Introduction
2 Preliminaries
3 Family Tree
4 Algorithm
5 Conclusion
References
A Parallel Construction of Vertex-Disjoint Spanning Trees with Optimal Heights in Star Networks
1 Introduction
2 The Star Graphs
3 Rescigno's Algorithm for Constructing VDSTs of Sn
4 An Amendatory Scheme
5 A Fully Parallelized Algorithm for Constructing VDSTs of Sn
6 Concluding Remarks
References
Protein Mover's Distance: A Geometric Framework for Solving Global Alignment of PPI Networks
1 Introduction
1.1 Our Contributions
2 Embedding Methods
2.1 Node2vec
2.2 Multi-dimensional Scaling
2.3 Structure Preserving Embedding
3 Protein Mover's Distance
4 Our Algorithms
4.1 Two PPI Networks
4.2 Multiple PPI Networks
5 Experiments
5.1 Datasets
5.2 Evaluation Metrics
5.3 Results
6 Conclusion
References
On the Profit-Maximizing for Transaction Platforms in Crowd Sensing
1 Introduction
2 System Model
2.1 Crowd Sensing System
2.2 Basic Definitions
2.3 Auction Mechanism
3 Problem Formulation
3.1 Participants' Utility Functions
3.2 Platform Profit Maximization Problem
3.3 Mathematical Deduction
4 Strategies and Algorithms for Platforms
4.1 Basic Case: One Requester and Multiple Providers
4.2 General Case: Multiple Requesters and Multiple Providers
4.3 Solutions for the General Case
5 Simulations
6 Conclusion
References
A New Approximation Algorithm for the Maximum Stacking Base Pairs Problem from RNA Secondary Structures Prediction
1 Introduction
2 Preliminaries
3 Algorithm Description
4 Performance Analysis
4.1 The Analysis of Approximation Performance Ratio
References
Approximation Algorithm and Graph Theory
Approximation Algorithms for the Generalized Stacker Crane Problem
1 Introduction
2 Algorithm GSC1
3 Algorithm GSC2
4 Algorithm GSC9/5
5 Conclusion and Future Work
References
Fast Approximation Algorithms for Computing Constrained Minimum Spanning Trees
1 Introduction
1.1 Related Works
1.2 Our Results
2 Algorithms for CMST via Bicameral Edge Replacement
2.1 Bicameral Edge Replacement
2.2 The Exact Algorithm
3 Proof of Theorem 7
4 Conclusion
References
Trajectory-Based Multi-hop Relay Deployment in Wireless Networks
1 Introduction
2 Problem Statement
2.1 System Model
2.2 Problem Definition
3 Demand Node Generation
3.1 Trajectory Matrix Generation
3.2 Prediction Matrix
3.3 Filtering
4 Submodular Iterative Deployment Algorithm (SIDA)
4.1 The SIDA
4.2 Performance Analysis
5 Simulations
6 Conclusion
References
A Local Search Approximation Algorithm for a Squared Metric k-Facility Location Problem
1 Introduction
2 Approximation Algorithm for the SM-k-FLP
2.1 Preliminaries
2.2 Local Search Algorithm
2.3 Analysis
2.4 Further Improvement by Scaling
3 Discussions
References
Combinatorial Approximation Algorithms for Spectrum Assignment Problem in Chain and Ring Networks
1 Introduction
2 Preliminaries
3 Approximation Algorithm and Its Performance Ratio Analysis
4 Conclusion
References
Mixed Connectivity of Random Graphs
1 Introduction
2 (k,)-connectivity
2.1 Proof of Theorem 1
2.2 Proof of Theorem 5
3 (k,)-mixed-connectivity
3.1 Proof of Theorem 3
3.2 Proof of Theorem 6
References
Conflict-Free Connection Numbers of Line Graphs
1 Introduction
2 Dynamic Behavior of the Line Graph Operator
3 The Values cfc(Lk(G)) of Iterated Line Graphs
References
The Coloring Reconfiguration Problem on Specific Graph Classes
1 Introduction
1.1 Our Problem
1.2 Known and Related Results
1.3 Our Contribution
2 Preliminaries
2.1 List coloring reconfiguration
2.2 Frozen Vertices
3 PSPACE-Completeness
3.1 List coloring reconfiguration
3.2 Reduction
3.3 Correctness of the Reduction
4 Polynomial-Time Solvable Cases
4.1 Split Graphs
4.2 Trivially Perfect Graphs
5 Conclusions
References
Combinatorial Optimization
Minimizing Total Completion Time of Batch Scheduling with Nonidentical Job Sizes
1 Introduction
2 Technical Preliminaries
3 Single Machine
4 Parallel Machines
References
New Insights for Power Edge Set Problem
1 Introduction
2 Preliminaries
3 Complexity Results
3.1 Hardness on Bipartite Planar Graphs of Degree Three
3.2 Extension of Hardness Result to Grid Graphs of Degree Three and Unit Disk Graph
4 Lower Bounds
4.1 Lower Bounds for Exact and FPT Algorithms
4.2 Non-approximability Results According to Complexity Hypothesis
5 Conclusion and Perspectives
References
Extended Spanning Star Forest Problems
1 Introduction
1.1 Graph Terminology and Definitions
1.2 Related Work
1.3 Organization and Contribution
2 Spanning Star Forest Problem: Minimization Case
3 Approximation Results
4 Spanning Star Forest Problem: Maximization Case
5 Conclusion
References
Faster and Enhanced Inclusion-Minimal Cograph Completion
1 Introduction
2 Preliminaries
3 Characterisation of Minimal Constrained Completions
4 An O(n+m') algorithm with incremental minimum
5 An O(n+m log2 n) algorithm
References
Structure of Towers and a New Proof of the Tight Cut Lemma
1 Introduction
2 Preliminaries
2.1 Notation and Definitions
2.2 Canonical Decomposition for General Factorizable Graphs
3 Towers and Tower-Sequences
4 A New Proof of the Tight Cut Lemma
4.1 Shared Definitions, Assumptions, Lemmas
4.2 When There Exists a Factor-Component in MinO(G) Whose Vertices are in Sc
4.3 When Every Factor-Component in MinO(G) has the Vertex Set Contained in S
References
On the Complexity of Detecting k-Length Negative Cost Cycles
1 Introduction
1.1 Related Works
1.2 Our Results
2 The NP-completeness of FPTkLNCC in Multigraphs
3 The NP-completeness Proof of kLNCC
4 Conclusion
References
A Refined Characteristic of Minimum Contingency Set for Conjunctive Query
1 Introduction
2 Preparation
2.1 Analysis of Previous Work
3 Results
4 Conclusion
References
Generalized Pyramidal Tours for the Generalized Traveling Salesman Problem
1 Introduction
2 Generalized Pyramidal Tours
3 Polynomial Time Solvable Subclass of GTSP on Grid Clusters
4 Conclusion
References
The 2-Median Problem on Cactus Graphs with Positive and Negative Weights
1 Introduction
2 Notations and Preliminaries
3 Parametric Problems L1 on Graphs
3.1 A Parametric Problem L1 on a Cycle
3.2 A Parametric Problem L1 on a Tree
3.3 A Parametric Problem L1 on a Cactus
4 Problems L2 on Cactus Graphs
4.1 Local 1-Median Problems
4.2 Algorithm for Local 1-Median Problems
References
The Eigen-Distribution of Weighted Game Trees
1 Introduction
2 Preliminary
3 Main Results
3.1 The Uniqueness of Ei(a,b)-Distribution w.r.t AD
3.2 The Uniqueness of Ei(a,b)-Distribution Fails w.r.t Adir
References
A Spectral Partitioning Algorithm for Maximum Directed Cut Problem
1 Introduction
2 Maximum Directed Cut Problem
2.1 Spectral Partitioning Rounding
3 The Spectral Partitioning Algorithm
4 Discussions
References
Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks
1 Introduction
2 Problem Formulation and Preliminaries
3 SVSP on Tree Network
3.1 Tour-Version of T-SVSP
3.2 Path-Version of T-SVSP
4 SVSP on Cycle Network
5 Conclusions
References
An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems
1 Introduction
2 Related Work
3 Model
3.1 General Model
3.2 Ordered Weighted Average and Generalized Gini Index
3.3 Fair Combinatorial Optimization
4 Alternating Optimization Algorithm
4.1 Optimality Condition and Approximation Ratio
4.2 Iterative Algorithm
5 Experimental Results
6 Conclusion
References
Efficient Algorithms for Ridesharing of Personal Vehicles
1 Introduction
2 Preliminaries
3 Dynamic Programming Algorithm
3.1 Algorithm
3.2 Analysis of Algorithm
4 Greedy Algorithm for Minimizing Number of Drivers
5 Concluding Remarks
References
Cost-Sharing Mechanisms for Selfish Bin Packing
1 Introduction
2 A Simple Mechanism
3 A Lower Bound of PoA
4 A Better Mechanism
5 Concluding Remarks
References
Application
Modelling and Solving Anti-aircraft Mission Planning for Defensive Missile Battalions
1 Introduction
1.1 Related Works
1.2 Objective, Contribution, and Outline
2 Problem Formulations
2.1 Problem Statement
2.2 Mathematical Formulations
2.3 NP-Hardness
3 Experiments
4 Conclusion
A Appendix
A.1 Compute e(b,f,t)
A.2 Compute t(b,l,f)
References
Perspectives of Big Data Analysis in Urban Railway Planning: Shenzhen Metro Case Study
1 Introduction
2 Urban Railway Datasets
2.1 Data of Passenger Travel Behavior
2.2 Dynamic Railway Card Data
3 Methodology
3.1 Utilization Efficiency of Rail Transit Analysis
3.2 Organization Efficiency of Traffic System Matching
3.3 Organization Efficiency from the Distribution of Work-and-Home
4 Conclusion
References
Cloning Automata: Simulation and Analysis of Computer Bacteria
1 Introduction
2 Cloning Automata
2.1 Fusion
2.2 Fission
3 Analysis of Cloning Automata
3.1 Analysis of Fusion
3.2 Analysis of Fission
4 Interruption of the Self-replication
5 Simulation and Analysis of Fork Bomb
5.1 Operational Principles of Fork Bomb
5.2 Simulation of Fork Bomb with CA
5.3 Analysis of Fork Bomb
5.4 Interruption of Fork Bomb
6 Conclusion
References
Research on Arrival Integration Method for Point Merge System in Tactical Operation
Abstract
1 Introduction
2 Construction of Multi-agent System for Merge Point Arrival
2.1 Aircraft Agent (AA)
2.2 Runway Control Agent (RCA)
2.3 Vertical Trajectory Agent (VTA)
2.4 Arrival Trajectory Agent (ATA)
2.5 Space Maintain Agent (SMA)
3 Module Design
3.1 Trajectory Generation Module
3.2 Trajectory Adjustment Module
3.3 Conflict Detection Module
4 Verification
5 Conclusions
References
Repair Position Selection for Inconsistent Data
1 Introduction
2 Preliminary
2.1 Basic Notations
2.2 Data Repair Strategies and the Repair Position Selection Problem
3 RPS Problem for Simple Deletion Strategy
4 RPS Problem for Full Modify Strategy
5 RPS Problem for Half Modify Strategy
6 Related Work
7 Conclusion
References
Unbounded One-Way Trading on Distributions with Monotone Hazard Rate
1 Introduction
2 One-Way Trading with Distribution
3 Distribution on the Highest Price Among All Buyers
3.1 Measure of E[OPT]E[ALG]
3.2 Measure of E[OPTALG]
4 Distribution on the Highest Price of Each Buyer
5 Concluding Remark
References
Generalized Bidirectional Limited Magnitude Error Correcting Code for MLC Flash Memories
1 Introduction
1.1 Bidirectional Limited Magnitude Channel Model
2 Preliminaries
3 Code Construction for (t+, t-) Bidirectional (lu, ld)--Limited Magnitude Error Correcting Codes
3.1 Encoding
3.2 Decoding
3.3 Size of the Code
3.4 Decoding Error Probability
3.5 Special Cases of the Code Construction 1
4 Conclusion
References
Optimal Topology Design of High Altitude Platform Based Maritime Broadband Communication Networks
Abstract
1 Introduction
2 Network Model and Problem Formulation
2.1 Network Model
2.2 Problem Statement
2.3 Problem Formulation
3 Numerical Analysis
4 Conclusion
Acknowledgments
References
On Adaptive Bitprobe Schemes for Storing Two Elements
1 Introduction
2 The Three Probe Adaptive Scheme
2.1 Our Scheme
3 Adaptive Scheme for Four Probes or More
3.1 Our Scheme
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Combinatorial Optimization and Applications

Description

More details

Other editions

Additional editions

Content

System requirements