Combinatorial Optimization and Applications

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

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

Xiaofeng Gao Hongwei Du Meng Han(Editor)

Springer (Publisher)

Published on 6. December 2017

XVIII, 529 pages

E-Book

PDF with digital watermarking

System requirements

978-3-319-71147-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 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
1 Introduction
2 Background
3 New Rota Rules and Safe Working Hours Fine
4 Example: Rostering Doctors in a Hospital Department
5 Approach
5.1 Hard and Soft Constraints
5.2 Generation of a Random Valid Roster
5.3 Optimisation. Simulated Annealing
6 Reference Problem Sets
7 Experimental Results
7.1 Example
7.2 Results for the Reference Problem Sets
8 Conclusion and Future Work
References
Bounds for Static Black-Peg AB Mastermind
1 Introduction
1.1 Previous Work
1.2 Our Contribution
1.3 Organization of the Article
2 Preliminaries
3 A Feasible O(n2)-Strategy for the Case n=p=c
4 A Feasible O(n1.525)-Strategy for the Case n=p=c
4.1 Possible Secrets with Low Hamming Distance
4.2 Possible Secrets with High Hamming Distance
5 A Lower Bound of (nlogN) for the Case n=p=c
6 An Optimal ( "4264306 4c/3 "5265307 -1)-Strategy for p=2
7 Optimal and Random Strategies and Future Work
References
Classification Statistics in RFID Systems
1 Introduction
2 Related Work
3 Problem Formulation
3.1 System Model
3.2 Problem Statement
4 Accelerating Gear I: Classification Subcarrier Allocation
4.1 Classification Design Overview
4.2 Classification Time Consumption Comparison
4.3 Impact: The Number of Subcarriers
5 Accelerating Gear II: Geometric Distribution Based Quantity Estimation
5.1 Statistics Design Overview
5.2 Quantity Estimation
5.3 Adaptive Estimation Time
6 Twin Accelerating Gears Realization
7 Performance Evaluation
7.1 Experimental Methodology and Setting
7.2 Performance Analysis
8 Conclusion
References
On the Complexity of Robust Stable Marriage
1 Introduction
2 Notations and Background
3 A Specific Problem Family
4 Complexity Results
5 Concluding Remarks
References
The Euclidean Vehicle Routing Problem with Multiple Depots and Time Windows
1 Introduction
2 Problem Description
3 QPTAS for Euclidean VRP with MDTW
3.1 Main Algorithm
3.2 Partitioning into Sub-instances
4 Theoretical Results and Proof
5 Conclusion and Future Work
References
Online Algorithms for Non-preemptive Speed Scaling on Power-Heterogeneous Processors
1 Introduction
2 Non-preemptive AVR
3 Small Density Ratio and Interval-Length Ratio
4 Arbitrary Interval Lengths and Densities
References
An Efficient Algorithm for Judicious Partition of Hypergraphs
1 Introduction
2 Problem Definition and Main Results
2.1 Problem Definition
2.2 Main Results
3 Algorithms for a Sub-problem
3.1 A Sub-problem of Judicious Partition of Hypergraphs
3.2 Approximation Algorithms for Solving the Sub-problem
4 Judicious Partition of Hypergraphs Algorithm
5 Conclusions
References
On Structural Parameterizations of the Matching Cut Problem
1 Introduction
2 Preliminaries
3 Graphs with Bounded Tree-Width
4 Graphs with Bounded Neighborhood Diversity
5 Other Structural Parameters
References
Longest Previous Non-overlapping Factors Table Computation
1 Introduction
2 Preliminary
2.1 String
2.2 Factor
2.3 Augmented Position Heap
2.4 Suffix Heap
2.5 LPnF Table
3 LPnF with Augmented Position Heap
4 LPnF with Suffix Heap
5 Conclusion
References
Modeling and Verifying Multi-core Programs
1 Introduction
2 Preliminaries
3 Operational Semantics of CCM
4 Modeling and Verifying Multi-core Programs with CCM
5 Case Study
6 Conclusion
References
Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel
1 Introduction
2 Preliminaries
3 Reduction Rules
4 Kernel Analysis
4.1 Analysis of Forest
4.2 Analysis of Cycles
References
On the Linearization of Scaffolds Sharing Repeated Contigs
1 Introduction
2 Obtaining Sequences from Solution Graphs
3 Unambiguous Solutions
4 Ambiguous Solutions
5 Conclusion
References
A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
1 Introduction
2 Memetic Algorithm
2.1 Main Scheme
2.2 Initial Population
2.3 Improved Local Search Procedure
2.4 Recombination Operator
2.5 Population Updating
3 Computational Results and Comparison
3.1 Computational Results
3.2 Comparisons with the State-of-the-Art Algorithms
4 Conclusion
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