Combinatorial Optimization and Applications : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II / / 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, 529 p. 88 illus.)
• Disciplina: 005.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
• Nota di contenuto: Intro -- Preface -- Organization -- Contents -- Part II -- Contents -- Part I -- Combinatorial Optimization -- Algorithms for the Ring Star Problem -- 1 Introduction -- 2 Exact and Approximation Algorithms for RSP -- 2.1 The Star -- 2.2 Fast Approximations -- 3 Heuristics for RSP -- 4 Simulation and Experiments -- 5 Approximation for Capacitated RSP -- 6 Conclusions -- References -- Price Fluctuation in Online Leasing -- 1 Introduction -- 2 Related Work and Background -- 3 Arbitrary Prices -- 4 The Progressive Model -- 5 Full Weather Forecast -- 6 Generalizations -- 7 Concluding Remarks and Future Work -- References -- Novel Scheduling for Energy Management in Microgrid -- 1 Introduction -- 2 Model Description -- 3 Maximizing the Renewable Energy Utilization -- 3.1 NP-Hard -- 3.2 Greedy Approximation Algorithm -- 4 Performance Evaluation -- 5 Conclusion -- References -- Improved Methods for Computing Distances Between Unordered Trees Using Integer Programming -- 1 Introduction -- 2 Preliminaries -- 2.1 Tree Edit Distance -- 2.2 Variants of Edit Distance -- 3 Previous Method [11] -- 4 Improved Method -- 4.1 Improved Method for Tree Edit Distance -- 4.2 Improved Methods for Variants of Edit Distance -- 5 Experiments -- 5.1 Glycan Dataset -- 5.2 CSLOGS Dataset -- 6 Conclusion and Discussion -- References -- Touring Convex Polygons in Polygonal Domain Fences -- 1 Introduction -- 2 Preliminaries and Definition -- 2.1 An Overview on the Continuous Dijkstra Paradigm -- 3 A Naive Algorithm -- 4 The Improved Algorithm: Ignoring Useless Wavelets -- 4.1 The Preprocessing Step -- 4.2 The Improved Algorithm -- 4.3 Complexity of the Algorithm -- References -- On Interdependent Failure Resilient Multi-path Routing in Smart Grid Communication Network -- 1 Introduction -- 2 Problem Statement -- 3 Variations of MNP -- 4 Polynomial-Time Reduction Between Variations. ; 5 Complexity of MNP -- 6 Concluding Remarks -- References -- An Improved Branching Algorithm for (n, 3)-MaxSAT Based on Refined Observations -- 1 Introduction -- 2 Reduction Rules and Some Properties -- 3 Branching Rules -- 4 Conclusion -- References -- Faster Algorithms for 1-Mappability of a Sequence -- 1 Introduction -- 2 Preliminaries -- 2.1 Suffix Array and Suffix Tree -- 3 Efficient Average-Case Algorithm -- 4 Efficient Worst-Case Algorithms -- 4.1 O(mn)-Time and O(n)-Space Algorithm -- 4.2 O(n logn loglogn)-Time and O(n)-Space Algorithm -- 5 Final Remarks -- References -- Lexico-Minimum Replica Placement in Multitrees -- 1 Introduction -- 2 Modeling Reliable Replica Placement in Multitrees -- 3 NP-Hardness of 3-LSP -- 4 Untangling Multitrees -- 5 Decomposing k-Multitrees -- 6 Optimizing LSP over a Decomposition Tree -- 7 Discussion -- References -- Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm Overview -- 4 Origin Graphs -- 5 NDLs of the Intermediate and Final Graphs -- 6 Finding a Subgraph Isomorphic to the Origin Graph -- 7 Bounding the Search Space and Time Complexity -- 8 Hardness Results -- 9 Conclusions -- References -- A New Graph Parameter to Measure Linearity -- 1 Introduction to a New Graph Parameter -- 2 Graph Families and Vertex Ordering Characterizations -- 3 Graph Classes with `39`42`"613A``45`47`"603ALexCycle= 2 -- 4 Conclusion and Perspectives -- References -- Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Listing Induced Subgraphs with Girth g -- 3.1 Basic Algorithm -- 3.2 Improved Algorithm -- 3.3 Weighted Case and Non-connected Case -- 4 Listing Edge Subgraphs with Girth g -- 5 Delay and Final Remarks -- References. ; Toward Energy-Efficient and Robust Clustering Algorithm on Mobile Ad Hoc Sensor Networks -- Abstract -- 1 Introduction -- 2 Related Work -- 3 Description of RE2WCA Algorithm -- 3.1 Energy Consumption Model -- 3.2 Mobility Measurement -- 3.3 Novel Weight Model and Hybrid Clustering Algorithm -- 4 Simulation Results and Discussion -- 5 Conclusions -- Acknowledgments -- References -- Game Theory -- The Cop Number of the One-Cop-Moves Game on Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Classical Cops-and-Robbers Game Versus the One-Cop-Moves Game on Planar Graphs -- 4 The Construction of the Planar Graph D -- 5 Some Preparatory Lemmas -- 6 The Robber's Winning Strategy: Proof of Theorem 1 -- 6.1 Case (A): U Contains Three Cops When dD(1,o) =1 -- 6.2 Case (B): U Contains Only 1 When dD(1,o) = 1 -- 6.3 Case (C): U Contains Exactly Two Cops When dD(1,o) = 1 -- 7 Concluding Remarks -- References -- The Price of Anarchy in Two-Stage Scheduling Games -- 1 Introduction -- 2 The Game Settings -- 3 The PoA in the Min-Max Model -- 3.1 The (S,M)-game -- 3.2 The (S,L)-game -- 3.3 The (L, M)-game -- 4 The PoA for Maximizing the Minimum Load -- 4.1 The (S,L)-game -- 4.2 The (S, M)-game -- 4.3 The (L,M)-game -- 5 Concluding Remarks -- References -- Selfish Jobs with Favorite Machines: Price of Anarchy vs. Strong Price of Anarchy -- 1 Introduction -- 1.1 Our Contribution -- 1.2 Related Work -- 2 Preliminaries -- 2.1 Model (Favorite Machines) and Basic Definitions -- 2.2 First Step of the Analysis (Reducing to Eight Groups of Jobs) -- 2.3 Conditions for SE -- 3 Strong Price of Anarchy -- 3.1 Notation Used for the Improved Upper Bound -- 3.2 The Actual Proof -- 4 Price of Anarchy -- 5 Conclusion and Open Questions -- References -- An Improved Mechanism for Selfish Bin Packing -- 1 Introduction -- 2 Preliminary -- 2.1 Selfish Bin Packing. ; 2.2 Mechanisms for Selfish Bin Packing -- 3 Modified Dutch Treatment (MDT) Mechanism -- 4 Upper Bound of the PoA -- 4.1 Weight Function w() and Its Properties -- 4.2 Relations Between w(L) and OPT(L) -- 4.3 Relation Between w(L) and NE(L) -- 5 Lower Bound of the PoA -- 6 Conclusion and Further Discussion -- References -- Approximation Algorithm and Graph Theory -- Hamiltonian Cycles in Covering Graphs of Trees -- 1 Introduction -- 2 Preliminaries -- 2.1 Terminology -- 3 The First Extension: The Same Label at Both Ends -- 3.1 Linear Time Recognition -- 4 The Second Extension: The Same Label at Two Consecutive Vertices -- 5 Miscellaneous Discussion: Relaxing the Restriction of Coprime Labels -- 6 Concluding Remarks -- References -- On k-Strong Conflict--Free Multicoloring -- 1 The Problem -- 1.1 Motivations and Previous Work -- 1.2 An Equivalent Formulation of Hypergraph Multicoloring -- 1.3 Our results in perspective -- 2 Mathematical preliminaries -- 3 Strong Conflict-Free Multicoloring Algorithm -- 3.1 1-SCF Multicoloring -- 4 Lower Bounds -- 5 Conclusion -- References -- Tropical Paths in Vertex-Colored Graphs -- 1 Introduction -- 2 Shortest Tropical Paths -- 2.1 Hardness Results for STPP -- 2.2 A Dynamic Programming Algorithm for STPP -- 3 Maximum Tropical Paths -- 3.1 Hardness Results for MTPP -- 3.2 An Algorithm for MTPP in Bipartite Chain Graphs -- 3.3 Algorithms for MTPP in Threshold Graphs -- 3.4 Algorithms for MTPP in Trees, Block Graphs and Interval Graphs -- References -- The Spectral Radius and Domination Number of Uniform Hypergraphs -- 1 Introduction -- 2 Preliminaries -- 3 Spectral Radius and Domination Number -- 4 Signless Laplacian Spectral Radius and Domination Number -- References -- Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals -- 1 Introduction -- 2 Definitions and Preliminaries. ; 3 NP-hardness of Skyline -- 4 Online Algorithms for Skyline When (i)=i -- 4.1 Bounded Length Intervals -- 4.2 Arbitrary Length Intervals -- 4.3 Lower Bound -- 5 Extensions -- 5.1 Uniform Color Capacity -- 5.2 Generalized Color Cost Function -- 5.3 Circular Graphs -- 6 The Permutation Problem -- 7 Conclusion -- References -- Approximating k-Forest with Resource Augmentation: A Primal-Dual Approach -- 1 Introduction -- 1.1 Our Approach and Contributions -- 1.2 Additional Related Work -- 2 Primal-Dual Algorithm for k-Forest -- 2.1 Hajiaghayi and Jain's LP for k-forest -- 2.2 Algorithm for k-Forest -- 2.3 Analysis -- 3 Conclusion -- A Alternate LP Rounding Based Algorithm -- References -- Parameterized Approximation Algorithms for Some Location Problems in Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Using a Layering Partition -- 4 Using a Tree-Decomposition -- 5 Implications for the p-Center Problem -- References -- Approximation Algorithms for Maximum Coverage with Group Budget Constraints -- 1 Introductions -- 1.1 Related Works -- 1.2 Our Results -- 2 A Simple Approximation Algorithm Based on Randomized LP Rounding -- 2.1 The LP Relaxation -- 2.2 A Randomized LP-Rounding Algorithm -- 3 An Improved Algorithm Based on Network Flow Modeling -- 3.1 Construction of the Auxiliary Graph -- 3.2 A Randomized Algorithm for MCG via Rounding Flows -- 4 A Randomized LP-Rounding Algorithm Based on Partitions -- 5 Conclusion -- References -- Application -- A Simple Greedy Algorithm for the Profit-Aware Social Team Formation Problem -- 1 Introduction -- 1.1 Other Related Works -- 2 Preliminaries -- 2.1 Variants of Social Compatibility -- 3 Our Greedy Algorithm -- 3.1 A Simple Charging Scheme -- 3.2 A Modified Charging Scheme -- 3.3 The Chaining Procedure -- 3.4 Hereditary Social Compatibility -- 4 Handling Task Multiplicity -- 5 Conclusion -- References. ; Doctor Rostering in Compliance with the New UK Junior Doctor Contract.
• 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-71147-4
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910484028503321
• Lo trovi qui: Univ. Federico II
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 10628