Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Combinatorial Optimization and Applications [[electronic resource] ] : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II / / edited by Xiaofeng Gao, Hongwei Du, Meng Han
| Combinatorial Optimization and Applications [[electronic resource] ] : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II / / edited by Xiaofeng Gao, Hongwei Du, Meng Han |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XVIII, 529 p. 88 illus.) |
| Disciplina | 005.3 |
| Collana | Theoretical Computer Science and General Issues |
| 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 |
| ISBN | 3-319-71147-4 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNISA-996466433803316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Combinatorial Optimization and Applications [[electronic resource] ] : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I / / edited by Xiaofeng Gao, Hongwei Du, Meng Han
| Combinatorial Optimization and Applications [[electronic resource] ] : 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I / / edited by Xiaofeng Gao, Hongwei Du, Meng Han |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XVIII, 483 p. 125 illus.) |
| Disciplina | 519.3 |
| Collana | Theoretical Computer Science and General Issues |
| 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 |
| ISBN | 3-319-71150-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNISA-996466432903316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
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
| 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 |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XVIII, 529 p. 88 illus.) |
| Disciplina | 005.3 |
| Collana | Theoretical Computer Science and General Issues |
| 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 |
| ISBN | 3-319-71147-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNINA-9910484028503321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
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
| 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 |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XVIII, 483 p. 125 illus.) |
| Disciplina | 519.3 |
| Collana | Theoretical Computer Science and General Issues |
| 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 |
| ISBN | 3-319-71150-4 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| 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. |
| Record Nr. | UNINA-9910484005703321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||