As a promising technique for offloading computation tasks from mobile devices, Unmanned Aerial Vehicle (UAV)- assisted Mobile Edge Computing (MEC) utilizes UAVs as computational resources. A popular method for enhancing the quality of service (QoS) of UAV-assisted MEC systems is to jointly optimize UAV deployment and computation task offloading. This imposes the challenge of dynamically adjusting UAV deployment and computation offloading to accommodate the changing positions and computational requirements of mobile devices. Due to the real-time requirements of MEC computation tasks, finding an efficient joint optimization approach is imperative. This paper proposes an algorithm aimed at minimizing the average response delay in a UAV-assisted MEC system. The approach revolves around the joint optimization of UAV deployment and computation offloading through convex optimization. We break down the problem into three sub-problems: UAV deployment, Ground Device (GD) access, and computation tasks offloading, which we address using the block coordinate descent algorithm. Observing the NP-hardness nature of the original problem, we present near-optimal solutions to the decomposed sub-problems. Simulation results demonstrate that our approach can generate a joint optimization solution within seconds and diminish the average response delay compared to state-of-the-art algorithms and other advanced algorithms, with improvements ranging from 4.70% to 42.94%.

Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor C/C-k approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system (i.e., the number of machines). Since C ≫ k in BFS, our result significantly improves the known best approximation ratio of (2C-k/C-k)(1-ϵ) for tight deadlines [17], and C/C-k · s/s-1/s for loose deadlines [18] on a slackness ratios > 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program (LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/C-k, and time complexity O(n ² + nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time approximation scheme (PTAS) when T is fixed.

Sweep coverage is an important covering technique in mobile crowdsensing, in which users or participants are employed to periodically monitor a set of points of interest (POIs) each with a weight indicating the value of its information to be collected. Traditionally, each user proposes a route along which there is a set of POIs to be monitored. The task is to select a set of participants such that the total weight of the monitored POIs is maximized. However, in real applications, users should have the flexibility to offer several preferred routes. This arises our studied maximum sweep assignment problem with flexibility, where each participant proposes several routes, and the new task is to strategically assign each participant a route among their choices in which the way maximizes the total weight of the monitored POIs. In this paper, we first prove that the problem is NP-complete and then devise two novel approximation algorithms with ratios 0.5 and 0.632. Experiments are also conducted to evaluate algorithms' practical performance. The results demonstrate that the proposed approximate methods are significantly faster (with up to two orders of magnitude runtime reduction) than the exact integer linear programming solution. In addition, we theoretically study another flexible sweep coverage model in which it costs to hire each user, and the goal is to cover all POIs multiple times (for more complete and accurate information) while minimizing the total hiring cost.