Combinatorial Optimization and Applications : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I / / edited by Xiaofeng Gao, Hongwei Du, Meng Han

• Pubblicazione: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017
• Edizione: 1st ed. 2017.
• Descrizione fisica: 1 online resource (XVIII, 483 p. 125 illus.)
• Disciplina: 519.3
• Soggetto topico: Algorithms; Computer science—Mathematics; Discrete mathematics; Numerical analysis; Artificial intelligence—Data processing; Computer networks; Software engineering; Discrete Mathematics in Computer Science; Numerical Analysis; Data Science; Computer Communication Networks; Software Engineering
• Persona (resp. second.): GaoXiaofeng; DuHongwei; HanMeng
• Note generali: Includes index.
• Nota di contenuto: 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.
• Sommario/riassunto: The two-volume set LNCS 10627 and 10628 constitutes the refereed proceedings of the 11th International Conference on Combinatorial Optimization and Applications, COCOA 2017, held in Shanghai, China, in December 2017. The 59 full papers and 19 short papers presented were carefully reviewed and selected from 145 submissions. The papers cover most aspects of theoretical computer science and combinatorics related to computing, including classic combinatorial optimization, geometric optimization, complexity and data structures, and graph theory. They are organized in topical sections on network, approximation algorithm and graph theory, combinatorial optimization, game theory, and applications.
• Titolo autorizzato: Combinatorial Optimization and Applications
• ISBN: 3-319-71150-4
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910484005703321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 10627