Intro
Preface
Organization
Contents
Approximation Algorithms
Constant-Approximation for Prize-Collecting Min-Sensor Sweep Coverage with Base Stations
1 Introduction
1.1 Related Work
1.2 Our Contribution
2 Problem Formulation and Preliminaries
3 A Primal-Dual Algorithm for PCFk
4 5-LMP for PCMSSC
5 Conclusion and Future Work
References
Approximation Algorithm for the Capacitated Correlation Clustering Problem with Penalties
1 Introduction
2 Preliminaries
3 Bi-criteria Approximation Algorithm and Analysis

3.1 Bi-criteria Approximation Algorithm
3.2 Theoretical Analysis
4 Conclusions
References
Approximation Algorithms for the Maximum Bounded Connected Bipartition Problem
1 Introduction
2 Preliminaries
3 2-BCBP
4 2-BCBP on an Interval Graph
5 Conclusion
References
An Approximation Algorithm for Solving the Heterogeneous Chinese Postman Problem
1 Introduction
2 Terminologies and Fundamental Lemmas
3 The Heterogeneous Chinese Postman Problem
4 Conclusion and Further Work
References
On Stochastic k-Facility Location
1 Preliminaries

2 Main Results
References
The Complexity of Finding a Broadcast Center
1 Introduction
2 Preliminaries
3 NP-Hardness of BCD
4 NP-Hardness of BCS
5 Properties of BC
6 Conclusion and Future Works
References
An Online Algorithm for Data Caching Problem in Edge Computing
1 Introduction
2 Related Work
3 System Model
4 Model Analysis
5 Conclusion and Future Work
References
Scheduling
Scheduling on Multiple Two-Stage Flowshops with a Deadline
1 Introduction
2 Preliminaries and Simple Facts
3 A Fast 4-Approximation Algorithm for MFL2-Packing

4 MFL2-Packing and Multiple-Knapsack
5 A (2+)-Approximation for mMFL2-Packing
References
Single Machine Scheduling with Rejection to Minimize the Weighted Makespan
1 Introduction
1.1 Scheduling with Rejection
1.2 Scheduling to Minimize the Weighted Makespan
2 Problem Formulation
3 NP-Hardness Proof
4 Dynamic Programming Algorithm
5 Approximation Algorithms
5.1 A 2-Approximation Algorithm
5.2 A Fully Polynomial-Time Approximation Scheme
6 Discussions on Some Special Cases
6.1 Problem 1^np=k^WCmax+JjRej
6.2 Problem 1^np=k^WCmax+JjRej

6.3 Problem 1^np=k^WCmax+JjRej
6.4 Problem 1^np=k^WCmax+JjRej
7 Conclusions and Future Research
References
Maximizing Energy Efficiency for Charger Scheduling of WRSNs
1 Introduction
2 System Model and Problem Formulation
2.1 Network Model
2.2 Energy Consumption Model
2.3 Problem Formulation
3 Algorithms for CS-MEE Problem
4 Simulation Results
5 Conclusion
References
A New Branch-and-Price Algorithm for Daily Aircraft Routing and Scheduling Problem
1 Introduction
2 Problem Description for DARSP
3 Branch-and-Price Strategies