Dr Jihong Yu

Dr Jia Liu

Dr Shen Peng

Dr Chuan Xu

Dr Yanpei Liu

Dr Yifei Zhu

Dr Rongrong Zhang

Dr Ruqi Huang

Dr Yue

Chuang Yu

Zejun Deng

Heng Li

Rupu Yang

Huan Xu

Prof Duyan Bi

Prof Dr Yuelei Xu

Linyuan

Chen, who illuminates my way to science. Thank him for giving me the opportunity to study for my doctorate four

Chapter 1 Introduction

This chapter provides a high-level description of the problems investigated in this thesis. It starts off by giving the background and motivation, then presenting the problems we address in this thesis, concluding with an overview of the organization of the thesis.

Background and Motivation

It is widely understood that communication and computing resources are potential bottlenecks in many emerging information systems. This is driven by the ever increasing number of communication and computing devices densely deployed today, which further underscores the necessity for efficient allocation and sharing of the common resources.

Scheduling is the process of allocating a pool of resources among a set of tasks such that specific predefined objectives are achieved or optimized. Being an important branch in combinatorial optimization and theoretical computer science [START_REF] Javadi | Analytical approaches for dynamic scheduling in cloud environments[END_REF][START_REF] Lawler | Chapter 9 sequencing and scheduling: Algorithms and complexity[END_REF][START_REF] Li | Process scheduling under uncertainty: Review and challenges[END_REF][START_REF] Van Dyke | Characterizing the manufacturing scheduling problem[END_REF], scheduling can be regarded as a decision-making process for optimizing one or more objectives.

In emerging computing and communication systems, the scheduling problems consider a set of tasks, each of which submits its request by requiring certain amount of specified resources for a specific time interval. The purpose of the problems is to optimally allocate limited resources to execute the tasks over time in order to achieve specific scheduling objectives, which can take many forms such as maximizing the system utility, minimizing makespan, minimizing the total delay cost, and so on [START_REF] Li | Process scheduling under uncertainty: Review and challenges[END_REF]. More precisely, a schedule is a subset of the Cartesian product of three sets [START_REF] Van Dyke | Characterizing the manufacturing scheduling problem[END_REF].

• A set of tasks (What) that should be executed.

• A set of time periods (When), intervals [start, end] with start ≤ end, where start and end are real-valued. Intuitively, one can associate with a task the time period during which it is executed.

• A set of resources that tasks occupy as they are executed. We denote this set as Where. It includes not only geographically localized resources, but also raw materials and other resources.

A schedule is a subset of What×When×Where. Intuitively, it specifies the resources that each task needs and when it needs them such that specific predefined objectives are achieved or optimized.

Unfortunately, most of scheduling problems are proven to be strongly NP-hard.

Thus, unless P=NP, there are no efficient algorithms to find optimal scheduling policy for such problems, where an efficient algorithm is one that runs in time bounded by a polynomial in its input size [START_REF] Williamson | The Design of Approximation Algorithms[END_REF]. A common approach for solving this problem is to relax the requirement of polynomial-time solvability. We try to find a scheduling policy that closely approximates the optimal scheduling policy in terms of system utility, but the goal is to relax the requirement as little as we possibly can.

In this thesis, we formulate and analyze a class of fundamental scheduling problems arising from a variety of emerging computing and communication systems, where tasks to be scheduled are partitioned into groups, and tasks in the same group can be batched and executed simultaneously. The goal is to design scheduling algorithms that maximize the system utility. Each of the problems, which is proven to be NP-hard, has its own particularities and calls for specific analysis that cannot draw upon existing results. For the considered problems, we consider approximation algorithms with proved performance guarantee.

Thesis Overview and Organization

In this section, we provide a high-level overview of our thesis. We first review the related literature in Chapter 2, and then describe the contributions of the thesis, which are presented sequentially in Chapters 3-5. Specifically, we start by investigating the baseline scenario of batching task scheduling problem in Section 3, and then we formulate and analyze the problems of downlink transmission scheduling with data sharing and contiguous-resource batching task scheduling, which are significant varieties and extensions of the baseline scenario of batching task scheduling problem, in Sections 4 and 5, respectively. Figure 1.1 illustrates the structure of our thesis. This chapter investigates the batching task scheduling problem in its baseline form and develops an algorithmic framework. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. We seek an optimal scheduling policy to maximize the overall system utility. We develop an algorithmic framework for the above scheduling problem in the generic form that can achieve 1/2-optimality, outperforming the best known result. The core technicality in our design is an adapted LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a 1/2-optimal feasible scheduling policy. We then demonstrate the application of our algorithmic framework to solve the generalized proportional broadcast problem by developing the first deterministic approximation algorithm outputting an l min /(2(l min + 1))-optimal scheduling policy, while there exist only randomized algo-rithms in the literature.

Batching Task Scheduling: Baseline Algorithmic Framework

Chapter 4: Downlink transmission scheduling with data sharing. This chapter formulates and analyzes a fundamental downlink transmission scheduling problem in a wireless communication system, composed of a base station, a set of transmission strategies and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. Compared to the baseline scenario of batching task scheduling, there are two particularities. First, each request can be served by a subset of transmission strategies. Second, requests should be served in the FIFO model. We seek a downlink transmission scheduling algorithm maximizing the overall system utility. In this chapter, we develop an algorithmic framework of the formulated downlink data transmission scheduling problem in both offline and online settings. We first establish its hardness, and then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings, respectively.

Chapter 5: Contiguous-resource batching task scheduling. This chapter formulates and analyzes the contiguous-resource batching task scheduling problem: a set of tasks need to be executed on a pool of continuous resource, and each task requires a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource; tasks are served in the FIFO manner. We seek an optimal resource allocation scheduling policy maximizing the overall system utility. In this chapter, we investigate both offline and online scheduling settings. In both cases, we establish the problem hardness and develop approximation algorithms with proven performance guarantee.

Chapter 2 Related Work

This thesis investigates a class of fundamental batching scheduling problems. From the algorithmic perspective, the problems we address are mostly related to the broadcast scheduling problem. This chapter reviews the related literature by starting with the broadcast scheduling problem in Section 2.1. We then extend the broadcast scheduling problem to the task scheduling problem by giving the overview of the task scheduling problems with and without batching in Section 2.2. To better understand the research status of the downlink transmission scheduling with data sharing and contiguousresource task scheduling problems we address in the thesis, we review the previous works on these two topics in Section 2.3 and Section 2.4, respectively. Section 2.5 concludes the chapter.

Before presenting the related work, we introduce the following definitions. Definition 2.1 (Feasible Scheduling Policy). We call a scheduling policy feasible for a problem if the policy satisfies all constraints of the problem. Definition 2.2 (Offline Scheduling Problem). The offline scheduling problem seeks an optimal feasible scheduling policy for the offline scheduler with the full knowledge of request/task information. Definition 2.3 (Online Scheduling Problem). The online scheduling problem seeks an optimal feasible scheduling policy for the online scheduler with only the current scheduling backlog.

In the analysis for the maximum problems, the standard definitions of approximation factor and competitive ratio, which are used to quantify the efficiency of any offline and online algorithm respectively, are provided as below.

Definition 2.4 (Approximation Factor). An algorithm Π is said to have approximation factor ρ > 1 if, for any problem instance σ, the system utility generated by Π, denoted by V Π (σ), is within factor ρ of the maximum system utility OP T (σ), i.e., ρ • V Π (σ) ≥ OP T (σ). We say that Π is a 1/ρ-approximation algorithm. Definition 2.5 (Competitive Ratio). An online algorithm Π is said to have competitive ratio ρ > 1 if, for any problem instance σ, the system utility generated by Π, denoted by V Π (σ), satisfies ρ • V Π (σ) ≥ OP T (σ). We say that Π is a 1/ρ-competitive algorithm.

Broadcast Scheduling

In the broadcast scheduling problem, a server broadcasts unit-size packets to a set of users, each requesting one of the packets with a time window, during which the requested packet needs to be received. Multiple users requesting a same packet can be served simultaneously if the packet is broadcast in the overlapped interval of their time windows. The problem faced by the central scheduler is to design a scheduling policy maximizing the system utility.

The broadcast scheduling problem has been considered in several papers. Gandhi et al. [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] developed a randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs and provided a 3/4-approximation for the problem where the profit of each task is a fixed value (i.e., the value does not change with the time), and provided a (1 -1/e)-approximation for the case where each task has an arbitrary time-window (instead of an interval) in which it must be processed, via a natural LP relaxation. Im and Sviridenko [START_REF] Im | New approximations for broadcast scheduling via variants of α-point rounding[END_REF] gave a randomized (0.5 -0.75/e)-approximation algorithm that improved the previous 3/4-approximation. Bansal et al. [START_REF] Bansal | Improved approximation algorithms for broadcast scheduling[END_REF] gave an algorithm with an approximation ratio of 6/5 without proof that was unfortunately wrong. Chekuri et al. [START_REF] Chekuri | New models and algorithms for throughput maximization in broadcast scheduling[END_REF] adapted the ideas of [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] to obtain a 3/4-approximation for profit maximization with unimodal profit functions and a (1 -1/e)-approximation for the case where each task is associated with an arbitrary non-negative profit function.

The broadcast scheduling problem can be regarded as a degenerated instance of each of our scheduling problems we address in this thesis.

Task Scheduling

Task Scheduling without Batching

Given a set of tasks, each of which is associated with a time window and, if admitted, needs to be executed within the window, the canonical task scheduling problem seeks a scheduling algorithm maximizing system utility, with the assumption that any pair of tasks cannot be executed simultaneously. This unbatching task scheduling problem has been considered in several related works [START_REF] Bar-Noy | A unified approach to approximating resource allocation and scheduling[END_REF][START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF][START_REF] Berman | Multi-phase algorithms for throughput maximization for real-time scheduling[END_REF][START_REF] Spieksma | On the approximability of an interval scheduling problem[END_REF]. Spieksma [START_REF] Spieksma | On the approximability of an interval scheduling problem[END_REF] considered the interval scheduling problem on a single machine. In the problem, the possible instances of a task are given explicitly as a set of time intervals. The goal is to pick a set of maximum number of nonintersecting time intervals so that at most one interval from each set of task instances is picked. This problem can be viewed as the discrete version for a special case of our problem. Spieksma [START_REF] Spieksma | On the approximability of an interval scheduling problem[END_REF] proved that the problem, to which the MAX 3-SAT-3 problem can be cast, is MAX-SNP hard, and gave a 1/2-approximation algorithm, and showed that the integrality gap of a linear programming formulation for this problem approaches 1/2 as well. Chuzhoy et al. [START_REF] Chuzhoy | Approximation algorithms for the job interval selection problem and related scheduling problems[END_REF] provided a randomized (1 -1/e)-approximation algorithm. Bar-Noy et al. [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] provided a deterministic approximation algorithm with approximation ratio 2 via LP that was implicit in the weighted case, and they also proved that the LP-based approximation algorithm achieved 1/3-approximation for contiguous input, where there are two instances of tasks so that one terminates within time slot t and the other starts within t.

Berman and DasGupta [START_REF] Berman | Multi-phase algorithms for throughput maximization for real-time scheduling[END_REF] proposed combinatorial two-phase algorithm that achieves ratio 2. Bar-Noy et al. [START_REF] Bar-Noy | A unified approach to approximating resource allocation and scheduling[END_REF] gave a 1/2-approximation algorithm via local ratio technique for discrete input and a 1/(2 + )-approximation algorithm for continuous input in the weighted case with arbitrary profits. Consider that tasks can be executed in multiple machines. In the case of unrelated machines, where the profit and processing time of each task are not identical in different machines, Bar-Noy et al. [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] demonstrated a greedy 1/2-approximation algorithm for the unweighted, and gave a 1/3-approximation factor for discrete weighted input and 1/4 for continuous weighted input. Bar-Noy et al. [START_REF] Bar-Noy | A unified approach to approximating resource allocation and scheduling[END_REF] achieved 1/2-approximation for discrete input and 1/(2 + ) for continuous input.

Berman and DasGupta [START_REF] Berman | Multi-phase algorithms for throughput maximization for real-time scheduling[END_REF] also gave a 1/2-approximation algorithm. In the case of K identical machines, i.e., where the profit and processing time of each task are the same for all machines, Bar-Noy et al. [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] achieved (1 -1/(1 + 1/K) K )-approximation for discrete input and (1 -1/(1 + 1/(2K)) K )-approximation for continuous weighted input. A (1 -(K/(K + 1)) K )-approximation algorithm was also implicit in Berman and DasGupta [START_REF] Berman | Multi-phase algorithms for throughput maximization for real-time scheduling[END_REF].

Task Scheduling with Batching

The works presented in Section 2.2.1 study a special case of the scheduling problem, where any pair of tasks cannot be executed simultaneously. In the generic scheduling problem, tasks are organized in groups such that those in the same group can be executed simultaneously. We call the simultaneously executed tasks a batch. The goal is to find a scheduling with batching that maximizes the total weight of the scheduled tasks. The number of tasks that can be batched simultaneously can be either bounded or unbounded. Both cases of the scheduling problem with batching are strongly NPhard. Bar-Noy et al. [START_REF] Bar-Noy | Throughput maximization of real-time scheduling with batching[END_REF] gave a 1/4-approximation algorithm that was based on the local ratio technique for discrete time input instance and 1/(4 + )-approximation for continuous time input instance in the bounded case. When the batch size is unbounded, the approximation factor for the algorithm provided by Bar-Noy et al. [START_REF] Bar-Noy | Throughput maximization of real-time scheduling with batching[END_REF] was reduced to 2 and (2 + ) for discrete and continuous time inputs, respectively. Moreover, they have extended the algorithm to multiple machines and obtained the same approximation factor.

Downlink Transmission Scheduling

The downlink transmission scheduling problem has been extensively explored in the telecommunication literature. In a typical formulation in wireless communication systems, the scheduler schedules packet transmission based on their requests and quality of service (QoS) requirements. The objective of the scheduler is to maximize the system utility. Many of the downlink transmission scheduling algorithms can be regarded as "gradient-based" algorithms. The key idea is to select the transmission rate vector to maximize the projection onto the gradient of the total utility [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF][START_REF] Agrawal | Optimality of certain channel aware scheduling policies[END_REF][START_REF] Huang | Downlink scheduling and resource allocation for OFDM systems[END_REF][START_REF] Mo | Fair end-to-end window-based congestion control[END_REF][START_REF] Stolyar | On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation[END_REF].

Delay is arguably the most common constraint in download scheduling. In this regard, Sandrasegaran et al. [START_REF] Sandrasegaran | Delay-prioritized scheduling (dps) for real time traffic in 3GPP LTE system[END_REF] proposed a delay-prioritized scheduling algorithm to support real-time traffic in the downlink 3GPP LTE system maximizing the system throughput. Neely [START_REF] Neely | Delay-based network utility maximization[END_REF] considered the problem of maximizing throughput with random packet arrivals and time-varying channel reliability, and designed a utility maximization algorithm that used explicit delay information from the head-of-line packet at each user.

More generically to address the general QoS requirements, Andrews et al. [START_REF] Andrews | Providing quality of service over a shared wireless link[END_REF] proposed an efficient way to support QoS of multiple real-time users sharing a wireless channel, and developed a scheduling policy to maximize channel capacity. Ryu et al. [START_REF] Ryu | Urgency and efficiency based packet scheduling algorithm for OFDMA wireless system[END_REF] proposed an urgency and efficiency based wireless packet scheduling algorithm to maximize throughput satisfying the QoS requirement, where the algorithm used the time-utility function as a scheduling urgency factor and the relative status of the current channel to the average one as an efficiency indicator of radio resource usage.

Song [START_REF] Song | Joint channel-aware and queueaware data scheduling in multiple shared wireless channels[END_REF] investigated downlink data scheduling with QoS provisioning over multiple channels, which, from a network point of view, provided line flexibility and granularity for resource allocation, and proposed corresponding scheduling algorithms achieving the maximum aggregate network utility. Ramli ea al. [START_REF] Ramli | Performance of well known packet scheduling algorithms in the downlink 3GPP LTE system[END_REF] investigated the performance of packet scheduling algorithms developed for single carrier wireless systems from a realtime video streaming perspective, and provided an algorithm achieving a high system throughput and supporting a large number of users by considering user fairness.

In more sophisticated settings, Rubio et al. [START_REF] Rubio | Joint optimization of power and data transfer in multiuser mimo systems[END_REF] formulated a general multi-objective optimization problem and presented an approach to solve the non-convex optimization problem in multiuser MIMO broadcast networks implementing simultaneous wireless information and power transfer. Eisen et al. [START_REF] Eisen | Learning optimal resource allocations in wireless systems[END_REF] considered the design of optimal resource allocation policies in wireless communication systems, modeled as a functional optimization problem with stochastic constraints, to maximize system utility; deep neural networks was trained with a primal-dual method to learn the resource allocation policy and optimize the primal/dual variables.

Bandwidth and Storage Allocation Problems

Consider the following generic setting. There is a set of independent users accessing a common frequency band whose width is F . Each user i submits its bandwidth request in the form of a quadruple (a i , d i , f i , l i ), where a i is the arrival time of the request and d i is the deadline before which the request needs to be served, f i with 0 < f i ≤ F is the quantity of frequency band requested by i, and l i is the number of slots the user requests to use the frequency band. If request i is served, a reward w i is generated to the system. The Bandwidth Allocation Problem (BAP) is to decide which requests to be served so as to maximize the total weight of total reward of served requests subject to the constraint that the total size of served requests at any time must not exceed capacity F and the frequency band allocated any request does not need to be contiguous [START_REF] Chen | Allocation of bandwidth and storage[END_REF].

The Storage Allocation Problem (SAP) is a variant of BAP, in which there are three additional constraints: (1) the specific portion of the resource allocated to a request cannot change during the time interval of the request, and (2) the allocation of resource must be contiguous, and (3) the two spatial intervals allocated to any two accepted requests should be disjoint if the reservation periods of the two requests intersect in their interior [START_REF] Bar-Yehuda | Approximation algorithms for bandwidth and storage allocation[END_REF]. In the above two problems, the frequency band allocated to any pair of requests should not overlap and d i -a i + 1 = l i for each request i.

Bandwidth Allocation Problem

The BAP has been extensively explored in the literature, however, without systematically taking into account spectrum reuse, a key difference compared to the problem we address in the Chapter 5. In different contexts, the BAP is termed differently, such as resource allocation [START_REF] Calinescu | Improved approximation algorithms for resource allocation[END_REF], resource-constrained scheduling [START_REF] Thiele | Resource constrained scheduling of uniform algorithm[END_REF], call admission control [START_REF] Gelenbe | Bandwidth allocation and call admission control in high-speed networks[END_REF], etc.. We refer the readers to these references for detailed description of the specific context and problem setting. Via LP rounding, Phillips et al. [START_REF] Phillips | Off-line admission control for general scheduling problems[END_REF] obtained a 1/6-approximation algorithm. By the local ratio technique, Bar-Noy et al. [START_REF] Bar-Noy | A unified approach to approximating resource allocation and scheduling[END_REF] provided a 1/4-approximation algorithm. Using a different idea, Chen et al. [START_REF] Chen | Allocation of bandwidth and storage[END_REF] provided a 1/3-approximation algorithm in the special case where the weight of each request i is (d i -a i )f i . Bar-Yehuda et al. [START_REF] Bar-Yehuda | Approximation algorithms for bandwidth and storage allocation[END_REF] presented a deterministic polynomial-time approximation algorithms, whose approximation factor was (2 + 1/(e -1)) ≈ 2.582.

Based on the LP relaxation, Calinescu et al. [START_REF] Calinescu | Improved approximation algorithms for resource allocation[END_REF] showed that the BAP could be (1/2 -)-approximated in polynomial time, which improved upon earlier approximation results. Darmann et al. [START_REF] Darmann | Resource allocation with time intervals[END_REF] considered a special case, where the rewards for all requests are identical, i.e., the goal is to maximize the number of served requests. They gave a deterministic (1/2 -)-approximation algorithm. Shachnai et al. [START_REF] Shachnai | Flexible bandwidth assignment with application to optical networks[END_REF] induced the flexible bandwidth allocation problem (FBAP), where each request consists of a minimal and a maximal resource requirement, for the duration of its execution, as well as a profit accrues per allocated unit of the resource. In FBAP, the goal is to assign the available resource to a subset of requests such that the total profit is maximized.

They presented a 1/3-approximation algorithm by adapting the local ratio technique for FBAP.

Storage Allocation Problem

A geometric expression of SAP is to interpret each request as an axis-aligned rectangle that has a fixed weight, a fixed size (height and length), and can be moved vertically but not horizontally. The goal is to pack a subset of non-overlapping rectangles in a rectangular frame of given size, so as to maximize the total weight of the chosen rectangles [START_REF] Chen | Allocation of bandwidth and storage[END_REF]. Phillips et al. developed a 1/35-approximation algorithm for the SAP.

Leonardi et al. [START_REF] Leonardi | Approximation algorithms for bandwidth and storage allocation problems under real time constraints[END_REF] obtained a 1/12-approximation algorithm. Bar-Nay et al. [START_REF] Bar-Noy | A unified approach to approximating resource allocation and scheduling[END_REF] gave an approximation algorithm that yielded an approximation factor of 7 based on the local ratio technique. Chen et al. [START_REF] Chen | Allocation of bandwidth and storage[END_REF] studied a special case where all resource requirements were multiple of 1/K for some integer K ≥ 1. They provided a polynomial-time approximation algorithm for the special case with an approximation factor of e e-1 by assuming that the maximum resource requirement of any request was O(1/K). Bar-Yehuda et al. [START_REF] Bar-Yehuda | Resource allocation in bounded degree trees[END_REF] gave a randomized 1/(2 + )-approximation algorithm, along with a deterministic ( e-1 2e-1 -)-approximation algorithm for any fixed > 0. Mömke and Wiese [START_REF] Mömke | A (2 + )-approximation algorithm for the storage allocation problem[END_REF] studied the generalized version of SAP, and presented a randomized LPbased approximation algorithm with expected performance ratio of 2 + for any > 0.

Shachnai et al. [START_REF] Shachnai | Flexible bandwidth assignment with application to optical networks[END_REF] introduced the flexible storage allocation problem (FSAP), which was a variation of FBAP, and presented a 1/(2 + )-approximation algorithm.

Conclusion

In this chapter, firstly, we have defined the offline and online scheduling problems and provided the standard definitions of approximation factor and competitive ratio, which are used to quantify the efficiency of any offline and online respectively. Then, we have reviewed the previous works on the problems of broadcast scheduling, task scheduling, downlink transmission scheduling, and bandwidth and storage allocation.

We have a more in-depth understanding of research status on the problems, based on which, the thesis investigates a class of batching task scheduling problems in its baseline form, and extends the baseline scenario of batching task scheduling problem to the problems of downlink transmission scheduling with sharing and contiguous-resource batching task scheduling. The thesis focuses on developing approximation algorithms with proved performance guarantee for the problems, which are proven to be NP-hard.

11

Chapter 3

Batching Task Scheduling: Baseline

Algorithmic Framework

This chapter investigates the batching task scheduling problem in its baseline form, where there is a set of tasks to be executed on a number of machines, and some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. The goal is to develop an optimal scheduling policy to maximize the overall system utility. We develop a baseline algorithmic framework for the above scheduling problem in the generic form that can achieve 1/2-optimality, outperforming the best known result [START_REF] Bar-Noy | Throughput maximization of real-time scheduling with batching[END_REF]. The core technicality in our design is an adapted LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a 1/2-optimal feasible scheduling policy, while the best existing result is a 1/4-approximation algorithm. We then demonstrate the application of our algorithmic framework to solve the generalized proportional broadcast problem by developing a deterministic approximation algorithm outputting an l min /(2(l min +1))optimal scheduling policy, while there exist only randomized algorithms in the literature.

Introduction

Consider the following canonical broadcast scheduling problem1 [START_REF] Chekuri | New models and algorithms for throughput maximization in broadcast scheduling[END_REF][START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF][START_REF] Im | New approximations for broadcast scheduling via variants of α-point rounding[END_REF]. A server broadcasts a set of unit-size packets to a set of users. Each user requests one of the packets with a time window, during which the requested packet needs to be received.

Multiple users can be served simultaneously if they request the same packet and the packet is broadcast in the overlapped interval of their time windows. The server obtains a unit reward for each served user. The problem faced by the server is to find an optimal scheduling algorithm maximizing her overall reward. This so-called pull-based broadcast scheduling problem has attracted significant research attention because of its neat formulation going far beyond the broadcast context and its profound algorithmic implication: it represents a class of scheduling problems concerning how to group requests over time so as to optimize or satisfy certain scheduling objective or constraint.

Another example fitting in the above formulation is the lock scheduling problem arising from concurrency control [START_REF] Tian | Contention-aware lock scheduling for transactional databases[END_REF]. In modern software and computing systems, objects (e.g., data, memory) are usually shared and concurrently accessed by a large number of applications or transactions, termed as tasks. Ensuring consistency of the shared objects in this context is of fundamental importance. A widely used mechanism is to rely on a lock manager to efficiently schedule the object access to ensure both data correctness and system efficiency. More specifically, consider an object accessed by multiple tasks, a task can access the object only if it is granted a lock. There are two types of locks: shared and exclusive locks. Shared locks are granted to tasks that do not modify the object, e.g., reading a data item in a database, while exclusive locks are given to tasks modifying the object, e.g., writing or updating a data item. The object can be accessed simultaneously by multiple tasks with shared locks, but only one single task with exclusive object. Given a number of tasks, each requiring to access the object within a certain period of time, the problem of lock scheduling consists of granting locks to them to maximize system utility, e.g., maximizing the number of executed tasks. Motivated by the above two examples, we formulate the following baseline scenario of batching task scheduling problem. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously by a single machine, while others require exclusive use of an entire machine. We seek an optimum scheduling policy to maximize the overall system utility.

• From a theoretical point of view, the baseline scenario of batching task scheduling problem is a significant generalization of the broadcast and lock scheduling problems. By casting the tasks into the packet requests such that the tasks that can be executed simultaneously correspond to the requests concerning the same packet to be broadcast, our problem degenerates to the broadcast scheduling problem.

By regarding the sharing of machines as shared locks, the task scheduling problem readily degenerates to the lock scheduling problem.

• From a practical point of view, the baseline scenario of batching task scheduling problem we formulate arises in a variety of engineering fields where computing, communication, and storage resources are potential bottlenecks and thus need to be carefully scheduled.

In this chapter, we establish an algorithmic framework on the above task scheduling problem in its most generic form. Our algorithmic framework allows to develop scheduling policies with guaranteed performance bound in a variety of scheduling contexts. Methodologically, we start with the baseline scenario without any assumption on the system setting to build our algorithmic framework in its generic form. We then demonstrate how our algorithmic framework can be adapted to solve other batch scheduling problems by analyzing the proportional broadcast scheduling problem, where a portion of the utility is obtained by a task even if it is not executed in totality.

Our main results in this chapter can be summarized as below.

• For the baseline scenario of batching task scheduling, we develop a 1/2-approximation algorithm, while the best existing result is a 1/4-approximation algorithm.

• For the proportional broadcast scheduling problem, we develop the first deterministic scheduling algorithm with constant approximation factor, while in the literature, there exist only randomized algorithms providing average performance guarantees.

System Model and Problem Formulation

System Model

As stated in the Introduction, we put the canonical broadcast scheduling problem in a generic context by considering the following task scheduling problem. We have a system composed of a set K of K machines, indexed from 1 to K. A set N of tasks, indexed from 1 to N |N |, are submitted to the system. Each task i is submitted at time a i , the release time, and should be finished by time d i , the deadline or due date; d i -a i + 1 is called its slackness. Let K i denote the set of machines, on each of which task i can be scheduled. For each machine k ∈ K i , we denote l i,k the execution time of task i on machine k. The tasks are divided into B non-overlapping groups, indexed from 1 to B; the tasks in the same group can be executed simultaneously on a same machine; we use b i (1 ≤ b i ≤ B) to denote the group index of task i; let N b ∈ N denote the set of tasks belonging to group b. If a task i is successfully executed on machine k before its deadline, a reward w i,k is generated to the system. For the tasks that can be executed simultaneously on a same machine, we say that they form a batch. Let π k ≤ N denote the maximum batch size that can be supported by each machine k, i.e., at most π k tasks of a same group can be executed simultaneously on each machine k.

The problem is called bounded if π k < N and unbounded otherwise. We seek an optimal scheduling policy to maximize the overall reward within a time horizon T . Table 3.1 lists the main notations in the chapter.

Problem Formulation

In practice, modern computing and communication systems operate on slotted time, where time is discretized into slots and scheduling is performed at the slot level. We thus concentrate ourselves on the discretized model, under which, by normalizing the slot duration to unit time, all the parameters and variables in the problem formulation are restricted to integers. In this case, our problem, denoted by P1, can be formulated as an integer linear programming (ILP) as below.

P1: maximize

i∈N k∈K i w i,k • x i,k subject to t j,k -t i,k ≥ l i,k , ∀i, j ∈ N , b i = b j , x i,k = x j,k = 1, t i,k < t j,k i∈N ,t i,k ≤t≤t i,k +l i,k -1 x i,k ≤ π k , ∀0 ≤ t ≤ T, 1 ≤ k ≤ K k∈K i x i,k ≤ 1, ∀i ∈ N a i ≤ t i,k ≤ d i -l i,k + 1, ∀i ∈ N , x i,k = 1, k ∈ K i x i,k ∈ {0, 1}, ∀i ∈ N , k ∈ K i .
where x i,k is the binary variable indicating whether task i is executed or not on machine k, and t i,k is the time to start executing task i on machine k if x i,k = 1. The first constraint implies that if task i cannot be executed simultaneously with task j on a same machine, i.e., b i = b j , the allocated time to execute them cannot overlap; The

G task graph G = (V, E) V i set of vertices of task i V i,k set of vertices in V i corresponding to machine k V i,k (t) set of vertices v ∈ V i,k with t v ≤ t ≤ t v + l v -1 V i,k,r set of vertices in V i corresponding to sub-machine r on machine k V i,k,r (t) set of vertices u ∈ V i,k,r with t u ≤ t ≤ t u + l u -1 t v start-time of the interval corresponding to vertex v l v length of the interval corresponding to vertex v w v weight of vertex v δ i,k d i -a i -l i,k + 2 δ i∈N k∈K i δ i,k y v
binary variable indicating whether vertex v is selected q b,t,k binary variable indicating whether a task of group b is executed at slot t on machine k q * b,t,k value of q b,t,k in the LP relaxation y * v value of y v in the LP relaxation N scaling factor. N = Rδ 1+ and δ 1+ for bounded and unbounded batching

C ordered set of 2 N -1 colors C b,t,k
set of colors already used to color the vertices v with t v ≤ t ≤ t v + l v -1 corresponding to group b and machine k V set of vertices output by Algorithm 1 second constraint indicates that at most π k tasks can be executed together at the same time on each machine k; The third constraint indicates that each task i is executed at most once; The fourth constraint is the time constraint to execute task i.

When K = 1 and π 1 = N , we can cast the Knapsack problem with integer weights to P1. It then follows from the NP-completeness of the Knapsack problem with integer weights [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF] that P1 is NP-complete.

Our Algorithmic Framework

Given the hardness of our problem, we naturally focus on developing approximate algorithm. At the high level, our idea is to construct a graph, termed as task graph, to capture the relationships between tasks and cast P1 to the Maximum Weighted Independent Set (MWIS) problem [START_REF] Sakai | A note on greedy algorithms for the maximum weighted independent set problem[END_REF] 2 in the task graph. To solve the MWIS, we construct an LP relaxation and solve the relaxed linear programming (LP) problem. By exploiting the structural properties of the task graph, we develop a coloring algorithm to find an independent set (IS) of the task graph that can map to a feasible scheduling policy, where we then prove the policy to be 1/2-approximation of the optimal solution of P1.

The feasible scheduling policy for the baseline scenario of batching task scheduling is defined as below, concisely termed as feasible policy.

Definition 3.1 (Feasible Scheduling Policy for the Baseline Scenario of Batching Task Scheduling). We call a scheduling policy feasible if

• each task is executed at most once;

• the time intervals for executing any pair of tasks from different groups do not overlap on a same machine;

• at most π k tasks of a same group can be executed simultaneously on each machine k.

Task Graph Construction

We divide each machine k into π k sub-machines. At most one task is allowed to be executed on each sub-machine at the same time. We then construct an undirected graph G = (V, E) capturing the relationships among tasks, termed as task graph, by defining its vertices and edges as below.

Vertices. Consider each task i ∈ N . For each sub-machine r (1 ≤ r ≤ π k ) on each machine k ∈ K i , we create a vertex v for each time interval of length l i,k in the time interval [a i , d i ]. We say that v covers i, and v corresponds to sub-machine r and machine k. If the scheduler decides to execute i on sub-machine r of machine k in the time interval corresponding to v, we say that i is instantiated by v. Let V i denote the set of vertices of task i; let V i,k,r denote the set of vertices in V i corresponding to sub-machine r and machine k. For each vertex v ∈ V i,k,r , we define a weight w v and assign w v to w i,k . Let t v and l v denote the left boundary (i.e., starting time) and the length of the time interval corresponding to vertex v.

Let π max 1≤k≤K π k . Denote δ i,k d i -a i -l i,k + 2 and δ i∈N k∈K i δ i,k .
For each task i, there are k∈K i π k δ i,k vertices in V i . We can thus upper-bound the number of vertices in G by πδ.

Edges. The edges in G capture the relationship among tasks and the number of tasks in each batch. We distinguish two types of edges.

Intra-task edges. For each task i, we construct an edge between each pair of vertices in V i . The intra-task edges model the constraint that any task is executed at most once.

Inter-task edges. This type of edges are further classified into two sub-categories.

• Inter-task edges characterizing conflicts among tasks. For each machine k and each pair of tasks i and j that cannot be executed simultaneously, i.e., b i = b j , we construct an edge between any pair of vertices v ∈ V i and u ∈ V j if v and u correspond to machine k and if the time intervals corresponding to v and u overlap, indicating that instantiating task i by v and instantiating task j by u cannot both happen in any feasible scheduling policy.

• Inter-task edges modeling bounded batching. For each machine k, each sub-machine r and each pair of tasks i, j with b i = b j and k ∈ K i ∩ K j , we construct an edge between each pair of vertices v ∈ V i,k,r and u ∈ V j,k,r if the time intervals corresponding to v and u overlap, making it impossible to instantiate i by v and also j by u.

From Task Scheduling to MWIS

We cast P1 to the MWIS problem [START_REF] Sakai | A note on greedy algorithms for the maximum weighted independent set problem[END_REF] in G. An IS of a graph is a set of vertices, no two of which are linked by an edge. The MWIS problem is to find an IS maximizing the sum of weights of the vertices in the IS. By choosing an IS in G we mean to execute the tasks instantiated by the vertices in the IS. We first show that there exists a one-to-one mapping between an IS of G and a feasible scheduling policy. To make our analysis more stream-lined, we put all the proofs in Appendix 3.8 and give proof sketch in the main text. Lemma 3.1. Each feasible scheduling policy maps to an IS of G, and vice versa.

Proof Sketch. The sufficiency proof consists of deriving a contradiction if there exists a feasible policy mapping to a subset of vertices in V containing two neighboring vertices.

The necessity proof is based on the construction of edges in G, where each type of edges ensures a kind of constraints for the feasible scheduling policy. Lemma 3.1 immediately leads to the following corollary.

Corollary 3.1. P1 can be cast to the MWIS problem on G, whose ILP formulation is given below.

max v∈V w v • y v s.t. y u + y v ≤ 1, ∀uv ∈ E y v ∈ {0, 1}, ∀v ∈ V
where y v is the binary variable indicating whether vertex v is selected in the IS.

LP Relaxation

Given the NP-hardness of the MWIS problem, we design an approximation algorithm by rounding the solution of LP relaxation of P1. To this end, we need to exploit the particular structure of our problem. This section is focused on the construction of the LP relaxation of P1.

We first replace the constraint y v ∈ {0, 1} with y v ≥ 0. It is well-known that the LP relaxation of the MWIS problem suffers the so-called half integer effect due to the edge constraint [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]. To mitigate this effect, we use the following constraints to replace the constraint y u + y v ≤ 1 such that (1) any feasible scheduling policy is still feasible in the relaxed problem, (2) non-feasible scheduling policies are eliminated as many as possible to facilitate the rounding process and to ensure the quality of the rounded integer solution.

• First, in any feasible scheduling policy, each task is executed at most once, leading to the following constraints.

v∈V i y v ≤ 1, i ∈ N . (3.2)
• Second, to model the resource constraint, we introduce a set of binary variable

q b,t,k , where b ∈ [1, B], t ∈ [0, T ] and k ∈ [1, K],
to indicate whether at least one task of group b is executed or not at slot t on machine k. In the LP relaxation we have 0 ≤ q b,t,k ≤ 1. Any pair of tasks from different groups cannot be executed simultaneously on each machine, leading to the following constraint.

1≤b≤B

q b,t,k ≤ 1, ∀0 ≤ t ≤ T, 1 ≤ k ≤ K. (3.3)
• Third, consider each machine k and each of its sub-machines r. In any feasible scheduling policy, for each slot t and each group b, at most one task belonging to group b can be served on the sub-machine if q b,t,k = 1. Therefore, the sum of y v 's of vertices v ∈ {V i,k,r (t)} i∈N b , which are adjacent to each other, is upper-bounded by q b,t,k , where V i,k,r (t) {u : u ∈ V i,k,r , t u ≤ t ≤ t u + l u + 1}. Mathematically we have the following constraint.

i∈N b v∈V i,k,r (t) y v ≤ q b,t,k , ∀1 ≤ k ≤ K, 1 ≤ r ≤ π k , 1 ≤ b ≤ B, 0 ≤ t ≤ T. ( 3
y v ≥ 0, ∀v ∈ V q b,t,k ≥ 0, ∀1 ≤ b ≤ B, 0 ≤ t ≤ T, 1 ≤ k ≤ K.
There is no need to explicitly add the constraints y v ≤ 1 and q b,t,k ≤ 1 since they are implied by (3.2) and (3.3), respectively. It is easy to see that any feasible scheduling policy is a feasible solution of P1'. Hence, an optimal fractional solution of P1' is an upper bound of the utility of any optimal feasible scheduling policy.

Constructing a Feasible Scheduling Policy: Rounding and Coloring

We now present our approximation algorithm that rounds the solution of P1' and constructs a feasible scheduling policy. Our approach generalizes the rounding and coloring technique developed in [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] adapted to our context, addressing the following two constraints in our problem: (1) task batching, (2) resource sharing. At a high level, we first solve P1', and then color the graph G based on the solution of P1' such that each color induces an IS that can be mapped into a feasible scheduling policy.

Let N πδ 1+ . To make our analysis concise, we assume that N is an integer, otherwise we need to round it to the nearest integer. Let C denote an ordered set (or a vector) of (2 N -1) colors. For each slot t, each machine k and each group b, let C b,t,k denote the set of colors already used to color the vertices v ∈ V with

t v ≤ t ≤ t v + l v -1
corresponding to group b and machine k.

We solve P1' and denote the solution by {y * v } v∈V , where y * v is the value of y v in the LP relaxation. Clearly, we have 0 ≤ y * v ≤ 1, ∀v ∈ V. Then, we color all vertices in V with as few colors as possible such that (1) each vertex v ∈ V receives N y * v colors, (2) any color used to any vertex v is not used to color any neighbor of v. Technically, we first sort the vertices in V non-decreasingly by their left boundaries, i.e., their starting time, with ties broken randomly. Step 2 is then executed in iterations. In each iteration, we color a vertex in V. For each vertex v ∈ V from left to right with respect to the above ordering. Let b denote the group to which the task covered by v belongs, and let The pseudo-code of our algorithm is given in Algorithm 1. Our algorithm outputs the set of vertices sharing one common color with maximum weight. As each vertex corresponds to a task, the final scheduling policy is to execute the tasks corresponding to these vertices. In the algorithm, we use the functions, which are briefly described as follows. As the functions are graph algorithms that can be coded straightforwardly, the detailed implementation is thus omitted in the pseudo-code.

• SameGroupColors(b, t, k, C) returns the set of colors in C already used to color the vertices u with t u ≤ t ≤ t u + u -1 corresponding to group b and machine k. Algorithm 1 Batching task scheduling: executed by the scheduler

1: Input: task graph G = (V, E), solution of P1' {y * v } v∈V , a vector C of (2 N -1) colors 2: Output: set of vertices in V
The corresponding scheduling is to execute the tasks corresponding to the vertices in V

3: sort the vertices in V non-decreasingly by their start-time, with ties broken randomly 4: for each v ∈ V with y * v N ≥ 1 from left to right with respect to the above ordering do end if 14: end for 15: Return set of vertices in V sharing one common color with maximum weight

Approximation Ratio Analysis

This subsection is dedicated to the theoretical analysis of our approximation algorithm. We first prove that each vertex v ∈ V with y * v N ≥ 1 is colored by y * v N colors in Lemma 3.2, based on which we further establish the approximation ratio of Algorithm 1 in Theorem 3.1.

Lemma 3.2. Each vertex v ∈ V with y * v N ≥ 1 is colored by y * v N colors by Algo- rithm 1.
Proof Sketch. For each vertex v ∈ V with y * v N ≥ 1, we prove that there are at least y * v N available colors in C that can be used by Algorithm 1 to color v. Theorem 3.1. Algorithm 1 outputs a 1 2 1 -1 δ -optimal feasible scheduling policy.

Proof Sketch. We establish the relationship between the IS output by Algorithm 1 and the utility of an optimal scheduling policy, which allows us to further bound the approximation ratio.

Asymptotically, by choosing a large δ, the approximation ratio of our algorithm approaches 2. Note that the best approximation ratio in the literature is 4 [START_REF] Bar-Noy | Throughput maximization of real-time scheduling with batching[END_REF].

We conclude this section by analyzing the complexity of Algorithm

The Case of Unbounded Batching

In this section, we describe how our algorithmic framework can be adapted in the unbounded case π k = N, ∀1 ≤ k ≤ K. Note that the unbounded batching task scheduling problem is still P-complete. Our objective is to adapt our algorithmic framework to produce a 1/2-optimal feasible scheduling policy.

Different from the bounded case, the bottleneck on the number of simultaneously executable tasks on any machine does not exist any more in the unbounded case. As a consequence, the task graph has simpler structure in the unbounded case; the LP relaxation process can then be adapted accordingly. The above adaptation enable us to derive the asymptotic approximation ratio of 2 in unbounded case. In the rest of this section, we briefly explain the main adaptation in the unbounded case.

Task Graph Construction

The task graph G = (V, E) is constructed below.

Vertices. Consider each task i ∈ N . For each machine k ∈ K i , we create a vertex v for each interval of length l i,k in the time interval [a i , d i ]. We say that v covers i and the machine corresponding to v is k. We denote V i the set of vertices covering i, and let V i,k denote the set of vertices in V i corresponding to machine k. For each vertex v ∈ V i,k , we define a weight w v and assign w v to w i,k .

Edges. We distinguish the types of edges.

• Intra-task edges. For each task i, we construct an edge between each pair of vertices in V i .

• Inter-task edges. Consider each machine k and any pair of tasks i, j ∈ N with b i = b j and k ∈ K i ∩ K j . For any pair of vertices v ∈ V i,k and u ∈ V j,k , we construct an edge between v and u if their corresponding time intervals overlap.

Based on the proof of Lemma 3.1, we can see that there exists a one-to-one mapping between an IS of G and a feasible scheduling policy for unbounded batching without conflict. The unbounded batching scheduling problem is thus transformed into finding a MWIS in G, the formulation of which is the same as in Corollary 3.1.

LP Relaxation

The construction of the LP relaxation in the unbounded case can be significantly simplified. For each slot t, let V i,k (t) denote the set of vertices v ∈ V i,k with t v ≤ t ≤ t v + l v -1. Consider each machine k. For each slot t and each group b, at any feasible scheduling policy, any task belonging to group b can be served at slot t on machine k if and only if q b,t,k = 1. Therefore, for each task i ∈ N , the sum of y v 's of vertices v ∈ V i,k (t) is upper-bounded by q b i ,t,k . Mathematically we have the following constraints.

v∈V i,k (t)

y v ≤ q b i ,t,k , ∀i ∈ N , 0 ≤ t ≤ T, 1 ≤ k ≤ K. (3.5)
We construct the following LP relaxation of the formulated MWIS problem.

y v ≥ 0, ∀v ∈ V q b,t,k ≥ 0, ∀1 ≤ b ≤ B, 0 ≤ t ≤ T, 1 ≤ k ≤ K.

Approximation Algorithm

Armed with the task graph and the LP relaxation, we then set N = δ 1+ in Algorithm 1. We first prove that each vertex v ∈ V with y * v N ≥ 1 is colored by ŷ * v N colors by Algorithm 1 in Lemma 3.3, based on which, we can establish the performance of Algorithm 1 in Theorem 3.2.

Lemma 3.3. Each vertex v ∈ V with y * v N ≥ 1 is colored by ŷ * v N colors by Algo- rithm 1.
Proof. For each vertex v ∈ V with y * v N ≥ 1, we prove that there are at least ŷ * v N available colors in C that can be used by Algorithm 1 to color the vertex.

We can then establish the performance bound of Algorithm 1 in the unbounded case. The proof follows the same way as that of Theorem 3.1. Theorem 3.2. Algorithm 1 outputs an asymptotically 1/2-optimal feasible scheduling policy for the unbounded batching scheduling problem.

In the single-machine case, i.e., K = 1, when the task slackness is constrained such that d i -a i + 1 < 2l i,1 for each task i, Algorithm 1 is a PTAS. This result implies that our algorithm is a PTAS for the canonical broadcast scheduling problem in this case.

Theorem 3.3. When K = 1, if d i -a i + 1 < 2l i,1 , ∀i ∈ N , Algorithm 1 is a PTAS.
Proof Sketch. We first prove that Algorithm 1 uses at most N colors to color all vertices in G. Then, we prove that Algorithm 1 outputs a (1 -1/δ )-optimal feasible policy.

Applying Our Algorithmic Framework to Solve Generalized Proportional Broadcast Scheduling Problem

In this section, we demonstrate how the developed algorithmic framework can be adapted to solve other scheduling problems. Technically, we consider the generalization of the proportional broadcast scheduling problem formulated in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] as described below.

Problem Statement

In the original proportional broadcast scheduling problem, we are given a set N of N tasks. Each task i is submitted at time a i , requires l i slots (the length of task i) to complete. The deadline of task i is d i . Different from the standard broadcast scheduling problem, each task does not need to be executed completely and the execution can be interrupted and can be resumed at the last execution point. A reward w i is generated to the system if task i is executed l i slots during the time interval [a i , d i ]. In the case where task i is not completely executed, the system still gets a reward that is proportional to the execution time γ i , i.e., w i (γ i ) = γ i l i w i . Tasks are divided into B non-overlapping groups. Tasks in the same group can be executed simultaneously. The goal is to maximize the total reward of the executed tasks. In the original formulation of Gandhi et al. [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF], the lengths of all tasks are identical, i.e., l i = l, ∀i ∈ N . A randomized approximation algorithm via dependent rounding scheme is proposed in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] achieving an expected approximation ratio 4l 4l-1 . Table 3.2 lists the notations used in Section 3.5.

In this section, we consider a generic formulation with heterogeneous task lengths.

We develop a deterministic approximation algorithm by integrating the idea developed in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] into our algorithmic framework. Our algorithm is the first deterministic algorithm for the proportional broadcast scheduling problem and achieves an asymptotic approximation ratio of 2(l min + 1)/l min , where l min min i∈N l i .

Our generalized proportional broadcast scheduling problem, denoted by P2, can be formulated below [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF].

P2 : max i∈N w i γ i l i s.t. d i t=a i q b i ,t ≥ γ i , ∀i ∈ N (3.6) 1≤b≤B q b,t ≤ 1, ∀0 ≤ t ≤ T (3.7) γ i ∈ {0, 1, • • • , l i }, ∀i ∈ N q b,t ∈ {0, 1}, ∀1 ≤ b ≤ B, 0 ≤ t ≤ T
where q b,t is a binary variable indicating whether at least one task of group b is executed or not at slot t. The first constraint ensures that whenever a task i is executed γ i slots, there are at least γ i time slots to execute the tasks of group b i during the interval [a i , d i ].

Table 3.2: Additional notations used in Section 3.5

γ i number of slots executing task i l i length of task i w i reward of task i if it is executed completed q b,t
binary variable indicating whether at least one task of group b is executed at slot t q * b,t value of q b,t in LP relaxation

T b set of slots {t 1 , t 2 , • • • , t m } such that t i < t i+1 , q * b,t i > 0 m b t∈T b q * b,t W b k window consisting of slot t with z b t,k > 0 G 0 bipartite graph G 0 = (U, V, E 0 ) G 1 bipartite graph G 1 = (U, V, E 1 ) G 2 bipartite graph G 2 = (U, V 2 , E 2 ) E 0 set of edges in G 0 E 1 set of edges in G 1 E 2 set of edges in G 2 U set of vertices, each of which corresponds to a slot u t vertex in U corresponding to slot t V set of vertices {v b 1 , v b 2 , • • • , v b m b } 1≤b≤B v b k vertex in V corresponding to group b and window W b k V 2 set of vertices in G 2 v i,k
vertex in V 2 corresponding to task i and window

W b i k z b t,k weight of the edge u t v b k in graph G 0 λ i d i -a i + 1 λ i∈N λ i N scale factor. N = λ 1+ for the proportional broadcast scheduling problem Ê set of edges output by Algorithm 2 Êi set of edges in Ê covering task i l min min i∈N l i γ * i value of γ i in LP relaxation w e weight of edge e in E 2
The second constraint ensures that any pair of tasks from different groups cannot be executed simultaneously.

The feasible scheduling policy for the generalized proportional broadcast scheduling is defined as below. Our objective in P2 is to find a feasible scheduling policy maximizing the system reward.

Definition 3.2 (Feasible Scheduling Policy for Generalized Proportional Broadcast Scheduling). We call a scheduling is feasible for generalized proportional broadcast scheduling if

• each task i ∈ N is executed at most l i slots;

• executions of any pair of tasks belonging to different groups do not overlap in time.

Deterministic Approximation Scheduling Algorithm

We first solve the LP relaxation of P2. To this end, we let all variables γ i and q b,t to be reals. Specifically, we replace the constraints

γ i ∈ {0, 1, • • • l i }, ∀i ∈ N with 0 ≤ γ i ≤ l i , ∀i ∈ N and q b,t ∈ {0, 1} by q b,t ≥ 0.
There is no need to explicitly add the constraint q b,t ≤ 1 since it is implied by (3.7).

The core part of our algorithm is to round the solution of the LP relaxation to a feasible scheduling policy. Gandhi et al. developed a randomized rounding algorithm in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF]. However, their algorithm assumes identical l i and only gives average performance guarantee. In order to design a deterministic scheduling algorithm, we apply our algorithmic framework, more precisely, the rounding and the related coloring technique we develop in previous sections. Our algorithm also integrates the idea used in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF] adapted in our context.

At a high level, our main idea is to construct a series of bipartite graphs, in which each edge captures the relationship between a slot and tasks of a same group. Each graph is constructed based on its predecessor to gradually arrive at a feasible scheduling policy. Instead of coloring vertices, our algorithm now colors the edges in the constructed graphs so that each color induces a matching of the graph or maps to a feasible scheduling policy. Specifically, our algorithm first constructs a bipartite graph G 0 based on the optimum solution of the LP relaxation. Then, we generate an auxiliary bipartite graph G 1 from G 0 , and we color the edges in G 1 such that each color induces a matching of the graph G 1 . Finally, we construct another edge-colored auxiliary bipartite graph G 2 based on the colored graph G 1 such that each color in G 2 induces a 29 feasible scheduling policy. The algorithm is composed of five steps, which are exposed sequentially. The first step essentially follows the procedures in [START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF], which are adapted below in the context of our problem.

Step 1: Construct a bipartite graph G 0 = (U, V, E 0 ). Let {γ * i } i∈N and {q * b,t } 1≤b≤B,0≤t≤T denote the solution of the LP relaxation of P2. G 0 contains two sets of vertices U and V, constructed as follows.

• Each vertex in U represents a time slot. Let u t denote the vertex in U corresponding to time slot t.

• Each vertex in V represents a group. For each group b, we seek the time slots, at each of which tasks of group b are executed fractionally in the LP solution, and we denote these time slots by

T b = {t 1 , • • • , t h , • • • }, where t h < t h+1 and q * b,t h > 0. We construct m b t=T b q * b,t vertices in V, denoted by {v b 1 , v b 2 , • • • , v b m b }. Each vertex v b k , 1 ≤ k ≤ m b
, corresponds to a window, denoted by W b k , as described later.

• Edges. Consider each group b. We group these slots into m b windows, denoted by

W b k , 1 ≤ k ≤ m b .
To this end, we recursively define non-negative numbers

z b t h ,k , 1 ≤ h ≤ |T b | and 1 ≤ k ≤ m b , as follows. z b t h ,k        A 1 if h-1 s=1 q * b,ts < k and h s=1 q * b,ts > k -1 0 otherwise
, where z b t h ,0 = 0 and

A 1 = min    q * b,t h -z b t h ,k-1 , 1 - t <t h ,t ∈W b k z b t ,k    . The time slots t with z b t,k > 0 form the window W b k . We can check that t∈W b k z b t,k = 1 for ∀1 ≤ k ≤ m b -1. In this regard, z b t h ,k represents the amount of fractional value to execute tasks belonging to group b at slot t h ∈ W b k . We connect each vertex v b k ∈ V, 1 ≤ k ≤ m b , to each vertex in U corresponding to time slots in the window W b k . The weight of the edge u t v b k is set to z b t,k .
The construction of G 0 is illustrated in

* b,t h , 1 ≤ h ≤ 7
, are 0.3, 0.3, 0.5, 0.5, 0.2, 0.9, 0.8

Step 2: Generate an auxiliary bipartite graph G 1 = (U, V, E 1 ). We construct G 1 by duplicating the vertices in G 0 . Let N λ 1+ , where λ i∈N λ i , and λ i d i -a i + 1. To make our analysis concise, we assume that N is an integer, otherwise we need to round it to the nearest integer. Concretely, for each edge Step 3: Color G 1 . We color each edge in G 1 by a color such that no adjacent edges are of the same color. Let C denote an ordered set of (2 N -1) colors. The coloring process runs in iterations. In each iteration, we color an edge using the first color in C not yet used to color any neighbor of it.

u t v b k ∈ E 0 , we construct z b t,k N new edges, each of which connects u t with v b k in G 1 ,
Step 4: Construct another edge-colored auxiliary bipartite graph

G 2 = (U, V 2 , E 2 ) based on G 1 . • Vertices in V 2 . Consider each task i ∈ N . For each integer k ∈ [1, m b i ], if the window W b i k includes at least one slot t ∈ [a i , d i ] with z b i t,k > 0, i.e., W b i k ∩ [a i , d i ] = ∅, we create a vertex v i,k , and add it to V 2 . • Edges in E 2 . Consider each task i and each integer k ∈ [1, m b i ]. If W b i k ∩ [a i , d i ] = ∅, for each slot t ∈ W b i k ∩ [a i , d i ], we choose an arbitrary set of min      z b i t,k N , max      0, l i N - <k k =1 t t =a i z b i t ,k N - t ∈W b i k ,t <t z b i t ,k N           colored edges in E 1 between u t ∈ U and v b i k ∈ V to connect v i,k ∈ V 2 with u t ∈ U
, and add them to E 2 . We say that these edges cover task i, and assign w i /l i as the weight for each of them. Let w e denote the weight of edge e in E 2 .

Step 5: Seek a set of edges, denoted by Ê, of the same color with maximum total weight and map them to a feasible scheduling policy. The final scheduling policy is to execute the tasks at the slots corresponding to the edges in Ê after a pruning process. To see the necessity of pruning Ê, let Êi denote the edges in Ê covering task i. We can upper-bound | Êi | by l i + 1. This is because there are at most l i N edges in E 2 covering i; hence the slots corresponding to the l i N edges belong to at most

l i + 1 windows W b i k , k ∈ [1, m b i ] by noticing t∈W b i k z b i t,k N = N , 1 ≤ k < m b i and t∈W b i m b i z b i t,m b i N ≤ N .
However, as each edge in Ê maps to a slot and each task i is executed at most l i slots, we need to remove an edge from Êi if | Êi | = l i + 1. We thus run a pruning procedure by removing the edge corresponding to the latest slot. We will prove in Lemma 3.5 that the edges in Ê after pruning map to a feasible policy.

The pseudo-code of our scheduling algorithm is given in Algorithm 2. The algorithm outputs a set of edges Ê. For each edge in Ê, one of its endpoints corresponds to a time slot, and the other point corresponds to a task. Thus, the final scheduling is to execute the tasks at the time slots corresponding to the set of edges output by Algorithm 2.

In the algorithm, the following functions are invoked. Their implementation is rather straightforward and omitted here.

• Color(e, C) returns the first color in C not yet used to color any neighbor edge of e.

• ExecutedSlots(b) returns an ordered set of slots

{t 1 , t 2 , • • • , t h , • • • }, t h < t h+1 ,
at each of which the tasks of group b are executed fractionally in the LP solution,

i.e, q * b,t h > 0.

• Edges(t, u t , v b k , E 1 ) returns an arbitrary set of min

     z b i t,k N , max      0, l i N - <k k =1 t t =a i z b i t ,k N - t ∈W b i k ,t <t z b i t ,k N           colored edges in E 1 between u t ∈ U and v b k ∈ V.
• MaxWeightEdges(E 2 ) returns the set of edges in E 2 of a same color with maximum weight.

• EdgesCoverTask(i, Ê) returns the set of edges in Ê covering task i.

• LatestEdge( Êi ) returns the edge in Êi corresponding to the latest slot.

Algorithm 2 Proportional broadcast scheduling: executed by the scheduler

1: Input: solution of LP relaxation of P2 {q * b,t } 1≤b≤B,0≤t≤T , N = λ 1+ , a vector C of 2 N -1 colors 2: Output: Ê
The scheduling is to execute the tasks at slots corresponding to the edges in Ê

3: U ← ∅, V ← ∅, E 0 ← ∅ Construct a bipartite graph G 0 = (U, V, E 0 ) 4: for each slot t do 5:
create a vertex u t , and add u t to U U consists of vertices representing slots 6: end for 7: for each group b do 8:

T b ← ExecutedSlots(b) 9: m b ← t∈T b q * b,t 10
:

for k = 1 to m b do 11:
create a vertex v b k , and add it to V 12:

W b k ← ∅ 13: for h = 1 to |T b | do 14: if h-1 s=1 q * b,ts < k and h s=1 q * b,ts > k -1 then 15: z b t h ,k ← min q * b,t h -z b t h ,k-1 , 1 -t <t h ,t ∈W b k z b t ,k 16:
else 17:

z b t h ,k ← 0 18: end if 19: if z b t h ,k > 0 then 20:
create an edge e between u t h and v b end for

25:

end for 26: end for

27: E 1 ← ∅ Construct an auxiliary bipartite graph G 1 = (U, V, E 1 ) 28: for each edge u t v b k ∈ E do 29:
construct N z b t,k edges between u t ∈ U and v b k ∈ V, and add them to E 1 30: end for 31: for each edge e ∈ E 1 do

Properly color the constructed edges 32:

color e using the color Color(e, C) 33: end for

34: V 2 ← ∅, E 2 ← ∅ Construct another auxiliary bipartite graph G 2 = (U, V 2 , E 2 ) 35: for each task i ∈ N do 36: for k = 1 to m b i do 37: if W b i k ∩ [a i , d i ] = ∅ then 38:
create a vertex v i,k , and add v i,k to V 2 39:

for t = min{W b i k ∩ [a i , d i ]} to max{W b i k ∩ [a i , d i ]} do 40: Ē ← Edges(t, u t , v b i k , E 1 ) 41: use the edges in Ē connect v i,k ∈ V 2 with u t ∈ U 42:
assign w i /l i to the weight for each of the edges in Ē end for 47: end for

48: Ê ← MaxWeightEdges(E 2 ) 49: for each task i ∈ N do
Prune the edges in Ê 50:

Êi ← EdgesCoverTask(i, Ê)

51: if | Êi | == l i + 1 then 52:
remove the edge LatestEdge( Êi ) from Ê

53:

end if 54: end for 55: return Ê

Approximation Ratio Analysis

In this subsection we derive the theoretical performance guarantee of Algorithm 2.

We first prove that all edges in E 1 are colored in Lemma 3.4, and Algorithm 2 outputs the set of edges mapping to a feasible scheduling policy in Lemma 3.5. We are then able to establish the approximation factor of Algorithm 2 in Theorem 3.4. We conclude this subsection by giving the complexity of Algorithm 2.

Lemma 3.4. All the edges in E 1 are colored by Algorithm 2.

Proof Sketch. For each edge in E 1 , we prove that there is at least one available color in C that can be used by Algorithm 2 to color the edge.

Lemma 3.5. The scheduling policy corresponding to the edges in Ê output by Algorithm 2 is feasible.

Proof Sketch. We first prove that any pair of tasks belonging to different groups are not executed simultaneously in the scheduling policy at the same slot. We then prove that there are at most l i time slots to execute task i in the scheduling policy. The feasibility of the output scheduling policy follows from the above results.

Theorem 3.4. Algorithm 2 outputs an asymptotic l min 2(l min +1) -optimal feasible scheduling policy.

Proof Sketch. We first establish the relationship between the total weight of Ê before pruning, i.e., Ê at line 48 of Algorithm 2, and the utility of the optimal scheduling policy. We then establish the relationship between the the total weight of Ê before and after pruning. Combining the above obtained result allows us to establish the l min 2(l min +1) -optimality of Algorithm 2.

To conclude this section, we analyse the complexity of Algorithm 2. Because there are at most λ i time slots at which each task i is executed fractionally in the LP relaxation, the number of time slots in

T b is O( i∈N b λ i ).

Numerical Analysis

In this section, we conduct numerical analysis to evaluate the performance of the constant-factor scheduling approximation algorithms we develop. In our simulation, we trace the following metric to evaluate the performance of the optimum scheduling policy compared to our algorithms:

Υ system utility of our algorithm system utility under optimal policy = total reward of requests served by our algorithm total reward of requests served by optimum policy (3.8) Specifically, we trace the maximal, average, and minimal values of Υ in our simulations. We simulate the baseline scenario of batching task scheduling problem including bounded case, unbounded case, and the problem of proportional broadcast scheduling, respectively.

Baseline Scenario of Batching Task Scheduling Problem

In our simulation, the time horizon T is set to 200, and there are 5 machines in the system. We set l max = 5 and l min = 1. We randomly choose the parameters

a i , d i , l i , b i , w i such that d i -a i + 1 ≥ l i , ∀i ∈ N
, and each request can be executed on any of machines. In the bounded batching case, the maximum batch size that can be supported by each machine is set to 10. In the unbounded batching case, the number of requests in each batch is no limit. We vary the number of requests N in the system from 50 to 500. For each N , we perform 50 simulation runs for each parameter setting.

The simulation results of the bounded case and the unbounded case are illustrated in From the simulation results, we make the following observations.

• Our algorithm achieves at least 76.84% of the optimal utility even in the worst case in the bounded case and at least 73.62% in the unbounded case, which are in accordance to the theoretical results we derive. • When the number of requests N increases, the performance gains slightly decrease, but our algorithm always maintains a good results.

• The small variances and confidence intervals indicate the reliability and stabilization of our algorithm.

Proportional Broadcast Scheduling Problem

In our simulation, the time horizon T is set to 200, and we set l max = 10 and l min = 1.

We randomly choose the parameters a i , d i , l i , b i , w i such that d i -a i +1 ≥ l i , ∀i ∈ N . We vary the number of requests N in the system from 50 to 500. For each N , we perform 50 simulation runs for each request parameter. The simulation results of the proportional broadcast scheduling problem are illustrated in Figure 3.3. Mean, variance confidence intervals (CI) are listed in Table 3.5.

From the simulation results, we make the following observations.

• Our algorithm achieves at least 92.08% of the optimal utility, which is in accordance to the theoretical result we derive.

• Wen the number of requests N increases, the performance gains also increase. This is because, when the number of requests is large, there are more opportunities to execute more tasks at each slot due to the nature of the proportional broadcast, which potentially improves the system performance.

Conclusion

Motivated by the classic broadcast scheduling problem, we have investigated a class of batching task scheduling problems in its baseline form. We have developed an algorithmic framework achieving 1/2-optimality, outperforming the best known result [START_REF] Bar-Noy | Throughput maximization of real-time scheduling with batching[END_REF].

The core technicality in our design is an adapted LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a feasible 1/2-optimal scheduling policy. We have then demonstrated the application of our algorithmic framework to solve the proportional broadcast problem. In this re-gard, we have developed the first deterministic approximation algorithm outputting a l min /(2(l min + 1))-optimal scheduling policy. We have complemented our theoretical analysis with numerical simulations that demonstrate the effectiveness of our algorithms. In the following chapters, we investigate two fundamental scheduling problems, which are significant varieties and extensions of the baseline scenario of batching task scheduling problem.

Appendix

Proof of Lemma 3.1

To prove that each feasible scheduling policy maps to an IS of G, assume by contradiction that there exists a feasible scheduling policy mapping to a subset of vertices V in G: among these vertices there are two neighboring vertices u and v connected by an edge denoted by e. In the construction of graph G:

• e cannot be an intra-task edge, otherwise u and v correspond to the same task, contradicting with the constraint that each task is executed at most once at any feasible policy.

• e cannot be an inter-task edge characterizing interference conflicts among tasks, otherwise u and v interfere with each other, contradicting with the constraint that the time intervals for executing any pair of interfere tasks on each machine never overlap at any feasible policy.

• e cannot be an inter-task edge modeling bounded batching, otherwise u and v correspond to the same sub-machine and the same machine, and their corresponding time intervals overlap, contradicting with the constraint that at most one task can be executed in each sub-machine of each machine at a same time.

The above analysis demonstrates that e cannot exist, thus proving via contradiction that each feasible scheduling policy maps to an IS of G.

We then prove that each IS of G maps to a feasible scheduling policy.

• The construction of intra-task edges ensures that for each task, at most one vertex covering it is chosen.

• The construction of inter-task edges characterizing conflicts among tasks ensures that the time intervals for executing any pair of interference tasks on each machine (e.g., tasks are not from the same group) never overlap.

• The construction of inter-task edges modeling bounded batching ensures that at most one task can be executed at each sub-machine of each machine at the same time, further ensures that each batch contains at most π k tasks on each machine k.

It then follows that each IS of G maps to a feasible scheduling policy.

Proof of Lemma 3.2

Consider any vertex v ∈ V with y * u N ≥ 1. Denote the task corresponding to v by i and the machine corresponding to v by k. Let q * b,t,k denote the value of q b,t,k in the LP relaxation. The neighbors of v can be divided into the following two classes.

The first class of neighbors consist of the vertices that are connected with v by inter-task edges. Consider the subgraph, denoted by G 1 , of G, in which we remove the intra-task edges from G. Clearly, G 1 includes all first class of v's neighbors.

When Algorithm 1 colors v, all vertices u ∈ V with t u < t v are already colored, while any vertex u ∈ V with t u > t v is not yet colored. Hence, any color, which cannot be used to color v, already occupied by the first class of neighbors must be already used to color some vertices u ∈ V corresponding to machine k with t u ≤ t v ≤ t u + l u -1.

Consider the time slot t v and each group b. For each sub-machine r of machine k, it follows from the constraint (3.4) that

j∈N b u∈V j,k,r (tv) y * u N ≤     u∈V j,k,r (tv),j∈N b y * u N     ≤ q * b,tv,k • N .
It then holds that the number of colors already used to vertices in {V j,k,r (t v )} j∈N b is upper-bounded by q * b,tv,k • N . Consider each group b. For any pair of sub-machines r 1 , r 2 , it follows from the construction of edges in G that any vertex in {V j,k,r 1 (t v )} j∈N b and any vertex in {V j,k,r 2 (t v )} j∈N b are not adjacent to each other in G 1 . Therefore, Algorithm 1 uses at most q * b,tv,k • N colors to color all vertices u in G 1 with t u ≤ t v ≤ t u + l u -1 corresponding to machine k and group b.

It follows from the constraint (3.3) that Algorithm 1 uses at most N colors to color

the vertices u in G 1 with t u ≤ t v ≤ t u + l u -1. Mathematically, 1≤b≤B q * b,tv,k • N ≤ 1≤b≤B q * b,tv,k • N ≤ N . (3.9)
Since the above analysis includes vertex v, we can upper-bound the number colors already used to color the neighbors of v in G 1 by N -y * v N . The second class of neighbors consist of the vertices that are connected with v by intra-task edges. Consider the subgraph, denoted by G 2 , of G, in which we remove the inter-task edges from G. For each task j, it follows from the constraint (3.2) that there are at most N vertices in G 2 covering task j. Mathematically,

u∈V j y * u • N ≤ u∈V j y * u • N ≤ N . (3.10)
For any pair of tasks j 1 , j 2 , there is no inter-task edge between any vertex in V j 1 and any vertex in V

Proof of Theorem 3.1

It is straightforward to observe that each color induces an IS of G. Denote the utility of an optimal scheduling policy by OP T . Let I * denote the IS output by Algorithm 1.

As each vertex v ∈ V is replaced by y * v N vertices, we have v∈I * w v ≥ N |C| v∈V w v y * v - v∈V w v N ≥ N |C| OP T - 1 δ max v∈V w v = N 2 N -1 OP T - 1 δ max v∈V w v .
As it holds trivially that OP T ≥ max v∈V w v . We then have

v∈I * w v ≥ N 2 N -1 1 - 1 δ OP T > 1 2 1 - 1 δ OP T.
The theorem is thus proved. The first class of neighbors consist of the vertices that are connected with v by inter-task edges. Consider the subgraph, denoted by G 1 , of G, in which we remove the intra-task edges from G. Any color, which cannot be used to color v, already occupied by the first class of neighbors must be already used to color some vertices u ∈ V corresponding to machine k with t u ≤ t v ≤ t u + l u -1. Consider the time slot t v and the machine k. For each task j ∈ N , it follows from the constraint (3.5) that u∈V j,k (tv)

y * u N ≤     u∈V j,k (tv) y * u N     ≤ q * b j ,tv,k • N . (3.11)
It follows from the above inequality that the number of colors already used to color vertices in V j,k (t v ) is upper-bounded by q * b j ,tv,k • N . Consider each group b. For any pair of tasks j 1 , j 2 ∈ N b , any vertex in V j 1 ,k (t v ) and any vertex in V j 2 ,k (t v ) are not adjacent to each other in G 1 . Therefore, Algorithm 1 uses at most q * b,tv,k • N colors to color all vertices u in G 1 with t u ≤ t v ≤ t u + l u -1 corresponding to machine k and group b.

It follows from (3.9) that Algorithm 1 uses at most N colors to color the vertices u

in G 1 with t u ≤ t v ≤ t u + l u -1.

Proof of Theorem 3.3

To prove the theorem, we first prove that Algorithm 1 uses at most N colors to color all vertices in G in the following lemma. Lemma 3.6. Algorithm 1 uses at most N colors to color all vertices in G.

Proof. Consider each vertex v ∈ V. Denote the task corresponding to v by i. As

d j -a j +1 < 2l j,1 , ∀j ∈ N , any already colored vertex u ∈ V i satisfies t u ≤ t v ≤ t u +l u -1.
Hence, any color, which cannot be used to color v, must be already used to color some vertices u ∈ V with t u ≤ t v ≤ t u + l u -1. For the time slot t v , each task j ∈ N and the machine k = 1, the number of colors already used to color the vertices in V j,1 (t v ) is upper-bounded by q * b j ,tv,1 • N because of (3.11). Consider each group b. For any pair of tasks j 1 , j 2 ∈ N b , any vertex in V j 1 ,1 (t v ) and any vertex in V j 2 ,1 (t v ) are not adjacent to each other in G. Therefore, Algorithm 1 uses at most q * b,tv,1 • N colors to color all vertices u ∈ V with t u ≤ t v ≤ t u + l u -1 corresponding to group b. It follows from the (3.9) that Algorithm 1 uses at most N colors to color the vertices u ∈ V with t u ≤ t v ≤ t u + l u -1 including vertex v. The lemma is thus proved.

Let I * denote the IS output by Algorithm 1. As each vertex v ∈ V is replaced by

y * v N vertices, we have v∈I * w v ≥ N N v∈V w v y * v - v∈V w v N ≥ OP T - 1 δ max v∈V w v .
As it holds trivially that OP T ≥ max v∈V w v . Because Algorithm 1 uses at most N colors to color all vertices in V , we then have

v∈I * w v ≥ 1 - 1 δ OP T.
The theorem is thus proved.

3.8.6 Proof of Lemma 3.4

Consider each edge u t v b t ∈ E 1 . The neighbors of u t v b t can be divided into two classes based on the construction of the bipartite graph G 1 .

• The first class of neighbors consist of the edges that are adjacent to

u t v b k because of vertex u t .
For the slot t, it follows from the constraint (3.7) that

1≤b≤B 1≤k≤m b z b t,k N -1 ≤ 1≤b≤B 1≤k≤m b z b t,k N -1 ≤ 1≤b≤B q * b,t • N -1 ≤ N -1
Thus, the number of the first class of neighbors is upper-bounded by N -1.

Therefore, when Algorithm 2 colors the edge u t v b t , the number of colors that have been used to color the first class of neighbors is upper-bounded by N -1.

• The second class of neighbors consist of the edges that are adjacent to

u t v b k because of vertex v b k . The window corresponding to vertex v b k is W b k . It follows from the definition of the windows that t∈W b k z b t,k ≤ 1, ∀b, k. Therefore, the total number of neighbors in E 1 because of v b k is at most N -1. Mathematically 0≤t≤T z b t,k N -1 ≤ 0≤t≤T z b t,k N -1 ≤ N -1.
Therefore, the number of colors used to color the second class of neighbors is upper-bounded by N -1.

By combining the above analysis, when Algorithm 2 colors the edge u t v b t , the number of colors that have been used to its neighbors is upper-bounded by 2( N -1). As |C| = 2 N -1, there is at least one available color that can be used by Algorithm 2 to color the edge u t v b t .

Proof of Lemma 3.5

To prove the lemma, we first prove that any pair of tasks belonging to different groups are not executed simultaneously by the scheduling policy at a same slot. For each slot t, any pair of edges, whose endpoints in U are u t , use different colors. Therefore, for any pair of edges in Ê corresponding to slot t, the tasks covered by them must belong to the same group, otherwise, the edges receive the different colors and cannot both belong to Ê. Therefore, the tasks are executed by the scheduling policy at the same slot must belong to the same group.

Then, it follows from Step 5 that there are at most l i edges in Ê covering task i.

Therefore, there are at most l i slots to execute task i in the final scheduling.

By combining the above analysis, we can derive that the scheduling policy is feasible.

Proof of Theorem 3.4

For each task i, it follows from the constraint (3.6) and the construction of G 0 that

d i t=a i q * b i ,t • N = 1≤k≤m b i t∈W b i k ,[a i ,d i ]∩W b i k =∅ z b i t,k • N ≥ γ * i • N . (3.12) Because each edge u t v b k ∈ E 0 is duplicated by z b t,k N edges in the construction of G 1 , it holds that z b t,k N -1 ≤ z b t,k N ≤ z b t,k N ≤ z b t,k N + 1.
Recall the construction of G 2 . There are min

     l i N , 1≤k≤m b i t∈W b i k ,[a i ,d i ]∩W b i k =∅ z b i t,k • N     
edges in E 2 covering task i.

There are at most λ i slots in the interval [a i , d i ] to execute the tasks belonging to group b i fractionally in the LP solution, and each slot belongs to at most two windows corresponding to the group b i . Therefore, there are at most 2λ i edges

u t v b i k in E 0 with z b i t,k > 0 and t ∈ [a i , d i ], 1 ≤ k ≤ m b i , i.e., 1≤k≤m b i |{t : t ∈ W b i k ∩ [a i , d i ]}| ≤ 2λ i .
The total weight of edges covering task i is

w i l i • min      l i N , m b i k=1 t∈W b i k ∩[a i ,d i ] z b i t,k • N      ≥ w i l i • min      l i N , m b i k=1 t∈W b i k ∩[a i ,d i ] (z b i t,k • N -1)      ≥ w i l i • min      l i N ,    m b i k=1 t∈W b i k ∩[a i ,d i ] z b i t,k • N    -2λ i      ≥ w i l i • f * N -2λ i • w i l i .
where the last inequality is because of (3.12) and l i ≥ γ * i . It follows from Lemma 3.4 that there are at most 2 N -1 colors in G 2 . For each color c, 1 ≤ c ≤ 2 N -1, let Ēc denote the set of edges in E 2 colored by c. We have

2 N -1 c=1 e∈ Ēc w e = i∈N w i l i • min    l i N , i∈N m b i k=1 t∈W b i k ∩[a i ,d i ] z b i t,k • N    ≥ i∈N f * w i l i • N -2λ i • w i l i = N i∈N f * w i l i - i∈N 2w i λ i /l i λ 1+ ≥ N i∈N f * w i l i - 2OP T λ ≥ N 1 - 2 λ OP T
The second inequality follows from i∈N

2w i λ i /l i λ 1+ ≤ max i∈N 2w i /l i λ ≤ 2OP T λ since executing
only the most valued task is a trivial feasible scheduling. The last inequality follows from that the value of an optimal fractional LP solution is an upper bound on the value of the feasible scheduling.

By convexity, the set of edges of the same color with maximum weight before pruning, denoted by Ê * , satisfy

e∈ Ê * w e ≥ N 2 N -1 1 - 2 λ OP T > 1 2 1 - 2 λ OP T
We then show the relationship between Ê output by Algorithm 2 and Ê * . For each task i ∈ N , it follows from Step 5 that at most one edge in Ê * covering task i is removed from Ê * , and the weight of the edge covering i is w i l i , which is at most 1 l i +1 of the total weight of the edges in Ê * covering task i. Therefore, it holds that e∈ Ê w e ≥ W ( Ê * ) -

1 l i + 1 W ( Ê * ) ≥ 1 2 (1 - 1 l i + 1 ) 1 - 2 λ OP T ≥ 1 2 (1 - 1 l min + 1 ) 1 - 2 λ OP T = l min 2(l min + 1) 1 - 2 λ OP T,
leading to an asymptotic approximation factor of l min /2(l min + 1).

47

Chapter 4

Downlink Transmission Scheduling with Data Sharing

This chapter formulates and analyzes a fundamental downlink transmission scheduling problem, which is a non-trivial extension of the baseline scenario of batching task scheduling problem, in a wireless communication system, composed of a base station, a set of transmission strategies and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. Each request can be served by a subset of transmission strategies, and requests need to be served in the FIFO model. We seek a downlink transmission scheduling algorithm maximizing the overall system utility. The above problem is termed as downlink transmission scheduling with data sharing problem.

Compared with existing works on the broadcast scheduling, batching task scheduling and the downlink transmission scheduling problems in Sections 2.1 to 2.3, the downlink transmission scheduling with data sharing problem has a stronger combinatorial flavor, as the scheduler needs to decide which subset of users to serve and under which transmission strategy. Moreover, the scheduling policy needs to comply with the FIFO model. Therefore, a dedicated algorithmic framework is called for which cannot be built on the existing models and approaches.

In this chapter, we develop an algorithmic framework of our downlink transmission scheduling with data sharing problem in both offline and online settings. We first establish its hardness by proving that (1) the offline problem is NP-hard, (2) the online problem is inapproximable in its generic form. Given the hardness result, we then develop approximation algorithms with mathematically proven performance guarantee.

Introduction

Consider the following fundamental downlink transmission scheduling problem in a generic wireless communication system composed of a base station and a set of users.

Each user requests a packet, which needs to be served within a time window. Some packets are requested by several users, thus creating the opportunity for serving them simultaneously by a single transmission due to the broadcast nature of the wireless medium. The base station can choose from a set of transmission strategies, e.g., in terms of combination of data rate and coding scheme, to serve the users, by taking into account the data sharing opportunities. Each request can be served by a subset of transmission strategies, e.g., those satisfying the SNR constraint related to the user.

When a user is served, a strategy-dependent utility is generated to the system. The problem faced by the base station is to design a downlink transmission scheduling algorithm maximizing the overall system utility.

The above downlink transmission scheduling problem significantly generalizes the canonical broadcast scheduling problem [START_REF] Chekuri | New models and algorithms for throughput maximization in broadcast scheduling[END_REF][START_REF] Gandhi | Dependent rounding and its applications to approximation algorithms[END_REF][START_REF] Im | New approximations for broadcast scheduling via variants of α-point rounding[END_REF], in which the base station can choose only a single transmission strategy. Our problem is intuitively more challenging due to the following two factors. Firstly, due to data sharing, we need to decide which subset of users to serve, and under which transmission strategy; this is by nature a combinatorial optimization problem which is notoriously difficult to solve. Secondly, the potential data sharing opportunity further accentuates the combinatorial flavor, as we need to decide whether to seize the opportunity, at the price of delaying the transmission of the shared packet and also the subsequent packets. From a communication system perspective, our problem involves two intertwined sub-problems: (1) admission control, i.e., which user requests to serve? (2) transmission optimization, i.e., which transmission strategy to use for each request?

Driven by the above design challenges, we embark in this chapter on an algorithmic study of the above generic downlink transmission scheduling problem. We investigate both offline and online settings. In both settings, we establish the hardness of the scheduling problem by proving that (1) the offline problem is NP-hard, (2) the online problem is inapproximable in its generic form. Given the hardness result, we then focus on developing approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios, respectively.

• In the offline setting, we devise an algorithmic framework by constructing a graph, termed as request graph, and mapping the offline problem to the MWIS problem in the constructed graph by integrating the specific constraints posed by our problem; we then solve the LP relaxation of the IS problem in the graph; we further develop a coloring-based algorithm that rounds the solution of LP relaxation to an integer solution mapping to a feasible scheduling policy; we mathematically establish its performance bound.

• In the online setting, we devise an iterative algorithm that greedily selects the most profitable requests and serves them under a least robust strategy covering the request; we prove that, as long as each request has a certain slackness (cf.

Section 4.4 for details), our algorithm can achieve a finite competitive ratio.

We further complement our theoretical analysis with numerical simulations that demonstrate the effectiveness of our algorithms in a variety of system settings.

The rest of this chapter is organized as follows. We formally state our downlink transmission scheduling problem in Section 4.2. In Section 4.3, we analyze the offline case and devise the scheduling algorithmic framework. In Section 4.4, we investigate the online case and present the design of an online scheduling algorithm. Section 4.5

conducts the simulation analysis evaluating the performance of our proposed algorithms.

Section 4.6 concludes the chapter.

System Model and Problem Formulation

System Model

We consider a time-slotted wireless communication system composed of a base station and a set N of N users. We focus on the downlink transmission from the base station to users. Specifically, each user requests a packet from the base station

i N b,t (i, j; r 1 , r 2 ) N + b,t (i, r 1 ) \ N + b,t (j, r 2 ) G request graph V set of vertices in G E set of edges in G w v weight of vertex v R i |R i | M max 1≤b≤B |N b | δ i d i -a i -min r∈R i τ r,b i + 2 δ i∈N δ i β i
priority under which request i is served β v priority of vertex v, a lower β value indicates higher priority t i starting time to serve request i t v starting time of the interval corresponding to v r i strategy under which request i is served r v strategy corresponding to v l v length of the interval corresponding to v y v binary variable indicating whether v is selected in the IS To improve transmission reliability and efficiency, the base station typically adapts its transmission parameters, e.g., data rate, coding schemes, etc. To make our analysis generic without relying on any particular system, we consider the setting where the base station disposes a set R of R transmission strategies (e.g., in terms of combination of data rate and coding scheme), from which it may choose. For a given transmission strategy r ∈ R, the transmitted packet can be decoded at user i if the SNR perceived by the user reaches a threshold. In this case, we say that user i can be reached or covered by strategy r. Let R i denote the set of transmission strategies covering request Hence, any user reached by a strategy can also be reached by a more robust strategy.

For any pair of strategies r and r , where r is less robust than r , we denote r ≺ r . We consider a typical case where ≺ is a strict total order over R such that we can rank all the strategies

r 1 ≺ r 2 ≺ • • • ≺ r R , and hence τ r 1 ,b < τ r 2 ,b < • • • τ r R ,b for each packet b.
For each request i, let r * i denote the least robust strategy in R i . If request i is served under strategy r, a reward w i,r is generated to the system. Under the above generic model, we are interested in seeking an optimal scheduling policy for the base station to maximize the total reward within a given time horizon T .

Problem Formulation

We are interested in both offline and online settings. In both cases the scheduler should follow the first-in-first-out (FIFO) service model such that admitted requests are queued at the scheduler in the same order they arrive and a request is cleared by the scheduler when the corresponding user is served. 2 Without loss of generality, we assume that a i ≤ a j for any 1 ≤ i < j ≤ N . In case where a i = a j and i < j, user i should be served first. Due to the broadcast nature of the wireless medium, the standard FIFO model needs to be tailored in our context. Definition 4.1 (Adapted FIFO Model). Any scheduling policy satisfying the following requirement is called an adapted FIFO model. When starting serving request i under strategy r at slot t, any low-priority request j > i requesting packet b i must be simultaneously served if r ∈ R j and a j ≤ t ≤ d j -τ r,b i + 1.

2 In case of tie, a predefined rule is applied to determine the service order. To illustrate our adapted FIFO model against the standard FIFO model policy, we consider an example composed of five requests (0, 1), (0, 3), (0, 3), (0, 6) and

(1, 3), indexed from 1 to 5, concerning the same packet, denoted by 1, where R =

{1, 2, 3}, R 1 = {1, 2, 3}, R 2 = {2, 3}, R 3 = {1, 2, 3}, R 4 = {3}, R 5 = {2, 3}, and
τ 1,1 = 1, τ 2,1 = 2 and τ 3,1 = 3.
For each request i ∈ {1, 2, 3, 4, 5} and each strategy r ∈ R i , the reward of request i under strategy r is 1, i.e., w i,r = 1. The lines in under strategy 1 at slot 0, requests 2 and 3 under strategy 2 at slot 1, request 4

under strategy 3 at slot 3, while rejecting request 5. Different from our adapted model, a request, if admitted, should be started no later than any admitted request arriving later. We can check that under the standard FIFO model, at most four requests can be served.

We remark that (1) the adapted FIFO model takes into account the packet transmission and is thus more flexible and naturally leads to better efficiency, as demonstrated by the illustration example, (2) it is technically more involved than the standard FIFO model. Our mathematical framework can be adapted if the standard FIFO model is employed.

In the adapted FIFO model, for a number of requests served simultaneously, among which the highest priority request is i, we say that these requests are served, or batched, under priority i, and we call i the head of the batched requests. In the degenerated case where i is served alone, its batch contains only itself, which is also the batch header.

We proceed by defining the feasible scheduling policy for downlink transmission scheduling, concisely termed as feasible policy in this chapter. We say that a feasible policy is optimal if it maximizes the system utility. We call a policy feasible if the following conditions are met.

• each request is served at most once;

• the base station does not transmit more than one packet simultaneously;

• the policy is an adapted FIFO model.

The Offline Case

In this section, we consider the offline downlink transmission scheduling problem, denoted by P3. We refer the readers to Appendix 4.7 for a detailed integer linear programming formulation of P3. In the following theorem, we prove that P3 is NPhard. To make our presentation more streamlined, we provide the proof sketch of the lemmas and theorems in the main text and assemble the detailed proof in Appendix 4.7. Proof Sketch. We prove that the classical 0-1 Knapsack problem can be reduced to P3.

Problem Hardness

It then follows from the NP-hardness of the 0-1 Knapsack problem that P3 is NP-hard.

It follows from the NP-completeness of Knapsack problem with integer weights that the discrete version of P3 is also NP-complete.

Given the hardness of P3, we devote our efforts to designing our approximation scheduling algorithm. Our central idea is to construct a graph, termed as request graph, to capture the relationships among requests, given the users' requests and the constraint imposed by the adapted FIFO model. We then cast P3 to the MWIS problem in the constructed request graph.

This section is organized as follows. We first construct the request graph and cast P3 to the MWIS problem in the graph. We then explore the structural properties of the constructed request graph to formulate the LP relaxation of P3. We further develop an approximation algorithm based on rounding the solution of the LP relaxation to an integer solution. The approximation ratio of our approximation algorithm is established to complete the section.

Request Graph

We start with a few definitions to simplify subsequent presentation. For any slot t and each strategy r, we call a user i active at t under r if r ∈ R i and

a i ≤ t ≤ d i -τ r,b i +1.
Intuitively, when starting serving user i at slot t under strategy r, the corresponding request can be finished by its deadline d i . We call a user active at slot t if there exists at least one strategy r ∈ R, under which the user is active, and we call slot t an active slot. Similarly, we call the packet b active at slot t if there is a user requesting packet b that is active at slot t. For any packet b, let N b denote the set of users requesting packet b and N b,t denote the set of users in N b active at slot t. For any user i ∈ N b,t and any strategy r, let N + b,t (i, r) denote the set of active users in N b at t under r whose indexes ≥ i, i.e., whose priorities are lower than or equal to that of i. Mathematically

N + b,t (i, r) {k : k ∈ N b,t , k ≥ i, a k ≤ t ≤ d k -τ r,b + 1}.
Similarly, define

N - b,t (i, r) {k : k ∈ N b,t , k ≤ i, a k ≤ t ≤ d k -τ r,b + 1}.
For any pair of users i, j ∈ N and any pair of strategies r 1 , r 2 ∈ R, we further define

N b,t (i, j; r 1 , r 2 ) N + b,t (i, r 1 ) \ N - b,t (j, r 2 ).
The request graph, denoted by G (V, E), consists of the following vertices and edges.

Vertices.

Each vertex in V maps to a time interval, a transmission strategy, and a priority, and each vertex covers a set of users. Consider each active slot t, each packet b corresponding to an active user at t, each user i ∈ N b,t , and each strategy r ∈ R i . We create the following two types of vertices.

• Type-1 vertices. For each user j ∈ N b,t with i < j, and each strategy r ∈ R\R i , we create a vertex, denoted by v, mapping to the time interval [t, t + τ r,b -1], the strategy r, and the priority i. Physically, the constructed vertex v corresponds to a possible execution of the requests in N b,t (i, j; r, r ) under strategy r. We say that v covers the requests in N b,t (i, j; r, r ). If the scheduler decides to start transmitting packet b under strategy r at slot t to serve the requests covered by v, we say that the requests in N b,t (i, j; r, r ) are instantiated by v. We define a weight w v for v and set w v k∈N b,t (i,j;r,r ) w k,r .

• Type-2 vertices. We create a vertex v mapping to the time interval [t, t+τ r,b -1],

the strategy r, and the priority i. It follows from the same notations as type-1 vertices that v covers the requests in N + b,t (i, r). We define its weight as w v k∈N + b,t (i,r) w k,r .

We use V i to denote the set of vertices covering user i. For each constructed vertex v, let t v and l v denote the starting time and the length of time interval corresponding to v, let r v denote the strategy of v, and let β v denote the priority of v. Note that a smaller β value indicates a higher priority. For all pair of users i, j ∈ N b,t and all pair of r, r with r ∈ R i and r ∈ R \ R i , further listing users in N b,t (i, j; r, r ) and

v 2 3 3 [0,1) v 3 2,3 2 [0,2) v 4 3 3 [0,2) v 5 2,3,4 2 [0,3) v 6 2,4 2 [0,3) v 7 3,4 3 [0,3) v 8 4 4 [0,3) v 9 2,3,5 2 [1,3) v 10 2,5 2 [1,3) v 11 3,5 3 [1,3) v 12 5 5 [1,3) v 13 3 3 [1,2) v 14 4 4 [1,4) v 15 3 3 [2,3) v 16 4 4 [2,5) v 17 4
N + b,t (i, r) takes O(|N b | 2 (R -|R i |)|R i |) = O(M 2 R 2 ) time.
For each packet b, there are at most k∈N b δ k slots at which packet b is active since there are δ k slots at which each request k is active. Therefore, the construction of the vertices can be completed in

O( 1≤b≤B k∈N b δ k M 2 R 2 ) = O(δM 2 R 2 ) time.

Edges.

The edges in G can be categorized into the following three types.

Inter-user edges (type-1 and type-2). For any pair of vertices u and v not covering any common user, we distinguish the following two subcategories.

• Type-1 edges. We construct an edge uv if the time intervals corresponding to u and v overlap each other, indicating the impossibility of instantiating the requests, which are covered by u, by u and also the requests, which are covered by v, by v.

• Type-2 edges. This type of edges are further classified into two cases, capturing our adapted FIFO model. Specifically, we construct an edge between any pair of nodes u and v if they satisfy the following conditions, with each set of conditions corresponding to a case.

β u < β v and t u > t v , or β u > β v and t u < t v .

-(1) the users covered by u and v request a same packet, (2) β v < β u , t v ≤ t u , and (3) there exists a request j covered by u with r v ∈ R j and a j ≤ t v ≤ d j -τ rv,b j + 1, i.e., request j fits into the time interval corresponding to v.

We clarify the implication of this case of edges via an example. Suppose the requests covered by v are instantiated by v. It follows from the adapted FIFO model that j must be served under the priority β v or batched with another request with higher priority than β v . Hence, the requests covered by v and request j cannot be both instantiated by v and u, respectively.

Intra-user edges (type-3). We construct an edge between each pair of vertices covering at least a same user, i.e., ∀u, v ∈ V i , uv ∈ E, ∀i ∈ N . The intra-user edges model the constraint that any user is served at most once.

We then analyze the complexity of creating the edges in G. Noticing that there are at most M requests in N b , 1 ≤ b ≤ B, it follows from the definitions of N b,t (i, j; r, r ) and N + b,t (i, r) that each constructed vertex covers at most M requests. Therefore, for each pair of vertices, checking whether the condition for the second case of type-2 edges is met takes O(M ) time. As the number of vertices in G is O(δRM ), the construction of the edges in G can be completed in O(δ 2 R 2 M 3 ) time.

From Downlink Transmission Scheduling to Maximum Weighted Independent Set

Armed with the constructed request graph G, we now prove that our offline scheduling problem can be cast to the MWIS problem of G. The following lemma establishes the relationship between the feasible policies and the ISes of G. By choosing an IS in G we mean to serve the requests covered by the vertices in the chosen IS. Proof Sketch. The proof of each IS mapping to a feasible policy follows from the construction of G, where each type of edges characterizes a constraint of the feasible scheduling policy. To prove that each optimal feasible policy maps to an IS of G, we consider an optimal feasible policy, and seek a subset of vertices in V covering all requests served by the optimal feasible policy. Based on the vertex construction, we prove that the subset of vertices is an IS. Therefore, each optimal feasible policy maps to an IS.

y v ∈ {0, 1}, ∀v ∈ V,
where y v is the binary variable indicating whether v is selected in the IS. Constraint (4.1)

states that any pair of neighboring vertices cannot be chosen together.

LP Relaxation

To solve the MWIS problem formulated above, we first solve the linear programming (LP) relaxation of MWIS problem and then round the fractional solution of LP relaxation to an IS. In this subsection, we develop an LP relaxation approach tailored to our problem. The next subsections are devoted to the rounding technique and the mathematical performance analysis.

V α (i) set of vertices v ∈ V with β v ≤ i and t v ≥ a i N α (i) set of users containing at least one vertex in V α (i) ϕ max k∈N (d k -a k + 1) l min min 1≤b≤B min r∈R τ r,b l max max 1≤b≤B max r∈R τ r,b N RM δ 1+ y * v value of y v in the solution of LP relaxation C ordered set (or vector) of colors
In the LP relaxation, for each vertex v ∈ V, we replace the constraint y v ∈ {0, 1} by y v ≥ 0. There is no need to explicitly add the constraint y v ≤ 1 since it is implied by the other constraints. We add the constraints v∈V i y v ≤ 1 indicating that each request i is served at most once. It is well-known that the LP relaxation of the MWIS problem suffers the so-called half integer effect due to the edge constraint [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]. To mitigate this effect, we construct the following two types of constraints to replace the edge constraint (4.1), where each type concerns a particular type of inter-user edges constructed in G, and thus is equivalent to the specific constraint of our scheduling problem.

Type-1 constraints. the priority of v is higher than or equal to the priority of i, i.e.,

β v ≤ i, (2) v is valid at slot a i , i.e., t v ≥ a i . Mathematically, V α (i) {v : v ∈ V, β v ≤ i, t v ≥ a i }.
Physically, the set of vertices in V α (i) includes all vertices v ∈ V satisfying: (1) the priority of v is higher than or equal to the priority of i, (2) v is connected with a vertex in V i by a type-2 edge. Let N α (i) denote the set of users containing at least one vertex in V α (i).

For each request i, any feasible scheduling policy can transmit at most max k∈N α (i) (d ka i + 1)/l min packets during the time interval [a i , max k∈N α (i) d k ] because the base station does not transmit multiple packets simultaneously. Therefore, there are at most max k∈N α (i) (d k -a i + 1)/l min vertices in V α (i) at any feasible scheduling policy, leading to the following constraint.

Type-2 constraints:

v∈V α (i) y v ≤ max k∈N α (i) (d k -a i + 1) l min , ∀i ∈ N . (4.3)
We now derive the complexity for establishing type-2 constraints. For each user i, there is at most one type-2 constraint. The complexity for listing all vertices in V α (i) is

O( k∈N b ,k≤i δ k RM ). Hence, listing type-2 constraints takes O( i∈N k∈N b ,k≤i δ k RM ) = O(M 2 R k∈N δ k ) = O(M 2 Rδ) time.
We now replace the edge constraint (4.1) by the above constructed constraints to formulate the LP relaxation of the MWIS problem, denoted by P3', as below.

P3': maximize v∈V w v y v subject to (4.2), (4.3)

v∈V i y v ≤ 1, ∀i ∈ N y v ≥ 0, ∀v ∈ V
By the analysis in this subsection, each optimal feasible scheduling policy is also a feasible solution of P3'. Hence, the value of an optimum fractional solution of P3' is an upper bound for the utility of the optimal feasible policy.

Approximation Scheduling Algorithm Design

Our approximation algorithm first solves P3' and then applies the rounding and coloring technique developed in [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] adapted to our context. To make our presentation streamlined and self-contained, we present and analyze the adapted rounding algorithm in the context of our problem. At a high level, our algorithm colors the graph such that each color induces an IS that can be mapped to a feasible scheduling policy. The algorithm essentially follows the procedures in [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF], which are adapted below in the context of our problem. Some additional notations are used in this subsection. We define ϕ max k∈N (d k -a k + 1). Let N = RM δ 1+ . To make our analysis concise, we assume that N is an integer, otherwise we need to round it to the nearest integer. Let C denote an ordered set (or a vector) of (1 + ϕ/l min ) N -1 colors.

We first solve P3' and denote the solution by {y * v } v∈V , where y * v is the value of y v in the LP relaxation. Clearly, we have 0 ≤ y * v ≤ 1, ∀v ∈ V. Then, we color the graph G such that (1) each vertex v ∈ V receives N y * v colors, and (2) any color used to color any vertex v is not used to color any neighbor of v. Technically, we sort the vertices in V non-decreasingly by their starting time with ties broken randomly. For each vertex v ∈ V from left to right, we use the first N y * v colors in C not used to color any neighbor of v to color v. The algorithm outputs the set of vertices sharing one common color with maximum weight.

The pseudo-code of our algorithm is given in Algorithm 3. As each vertex corresponds to a request, the final scheduling is to serve the requests corresponding to the set of vertices output by Algorithm 3. In the algorithm, the function Color(v, y * v , C) returns the first N y * v colors in C that have not been used to color any neighbor of v. Color is a graph algorithm that can be coded straightforwardly. The detailed implementation is thus omitted in the pseudo-code.

Algorithm 3 Offline downlink transmission scheduling: executed by the scheduler 1: Input: request graph G = (V, E), solution of the LP relaxation {y * v } v∈V , N ← RM δ 1+ , a vector C of (1 + ϕ/l min ) N -1 colors 2: Output: set of vertices

The final scheduling policy is to serve requests corresponding to V

3: sort the vertices in V non-decreasingly by their starting time, breaking ties randomly 4: for each v ∈ V from left to right do 5:

color vertex v using the colors Color(v, y * v , C) 6: end for 7: return set of vertices in V sharing one common color with maximum weight

Performance Analysis

In this subsection we derive the theoretical performance guarantee of our approximation algorithm. We first prove that each vertex v ∈ V with y * ϕ/l min ) N ISes of G. We prove that there exists an IS whose total weight is at least 1/(1 + ϕ/l min ) of the utility for the optimal feasible scheduling policy. Theorem 4.2 demonstrates that the approximation factor of our algorithm only depends on the ratio between the largest task slackness and l min , i.e., its performance does not degrade with the system size.

To conclude the analysis of our algorithm, we analyze its complexity. To that end, we firstly need to compute the number of vertices in V. To that end, we can calculate that the number of created vertices in V is at most δRM . The number of colors received by each vertex is O( N ), and thus the complexity of the color process is O(RM δ N ).

The complexity of the sorting process is O(RM δ log(RM δ)). Therefore, It follows from N = RM δ 1+ that the complexity of our algorithm is O(R 2 M 2 δ 2+ ).

The Online Case

In this section, we consider the online scheduling problem, where the scheduler only knows the current scheduling backlog. More specifically, the parameters a i , d i , b i , R i for request i are known only at the moment of arrival. As the offline case, the online downlink scheduling problem also takes into account our adapted FIFO model. Table 4 In the online setting, we focus on the non-preemptive scheduling model: once a request starts being served, it must be completed without interruption [START_REF] Fung | Laxity helps in broadcast scheduling[END_REF] [START_REF] Hoogeveen | On-line scheduling on a single machine: maximizing the number of early jobs[END_REF]. We note that the non-preemptive model is seamlessly compatible with our adapted FIFO model.

Problem Inapproximability

We start by showing in the following theorem that the online problem in its generic form cannot be approximated with any finite competitive ratio. Theorem 4.3. For any ρ > 0, there exists an instance of our scheduling problem, where the competitive ratio of any deterministic online algorithm Π is larger than ρ.

B max max 1≤t≤T |B(Ω t )|. We use a quadruple (i, t i , r i , β i ) to denote each served request i, where t i is the starting time to serve request i, r i and β i are the strategy and the priority under which i is served.

The pseudo-code of our algorithm is given in Algorithm 4. Consider the current slot t. If the slot t is not free or there is no ready request at slot t, i.e., Ω t = ∅, there is no request that starts being served at slot t; otherwise, for each packet b ∈ B(Ω t ), we first seek the least robust strategy r b that can reach all users in Ω t requesting packet b, We briefly describe the following functions used in our algorithm, which can be coded straightforwardly. The detailed implementation is thus omitted in the pseudo-code.

• Packets(Ω) returns the set of packets, each of which is requested by at least one user in Ω.

• UsersRequestPacket(Ω, b) returns the set of users requesting packet b.

• LeastRobustStrategy(Ω) returns the least robust strategy r that can reach all requests in Ω, i.e., r = argmin r∈R i ,i∈Ω τ r,b .

• TotalReward(Ω, r) returns the total reward of requests in Ω under strategy r.

• HighestPriorityRequest(Γ) returns the highest priority request in Γ.

Algorithm 4 Online downlink transmission scheduling: executed by the scheduler at each slot t 1: Input: Ω t : the set of ready requests at slot t 2: Output: N * t , the set of requests started being served at slot t, with each admitted request i served under strategy r i and priority β i 3: Initialization:

N * t ← ∅ 4: if Ω t == ∅ then 5: return ∅ 6: end if 7: B(Ω t ) ← Packets(Ω) 8: Γ ← ∅
Γ stocks the set of users that start being served at slot t 9: r = 1 r, initialized by strategy 1, is the index of the strategy, under which users in Γ are served scheduling policy compared to our algorithms. Specifically, we trace the maximal, average, and minimal values of Υ in our simulations.

In our simulations, the time horizon T is set to 200. For each strategy indexed by r, the number of time slots to transmit each packet is r under strategy r. We simulate three typical scenarios, in each of which we vary the number of requests N in the system from 50 to 500. For each N , we perform 50 simulation runs for each request parameter setting.

Scenario 1

In the first scenario, we randomly choose the parameters a i , d i , b i , R i such that d i - From the simulation results, we make the following observations.

a i + 1 ≥ min r∈R i τ r
• Our algorithms achieve at least 43% of the optimal utility even in the worst case in the offline setting and at least 33% in the online setting, which demonstrate the theoretical results we derive.

• Our offline algorithm performs better compared to our online algorithm, as the base station has the full knowledge of request information in the offline setting and naturally achieves better performance.

• When the number of requests N increases, the average performance gain first decreases in both offline and online settings, and then stabilize, indicating that the resource pool approaches its capacity limit.

• The smaller the number of packets there is, the better performance our algorithms achieve. This is because, when the number of packets is small, there are more opportunities for serving requests simultaneously, which potentially improves the system performance.

Scenario 2

In this scenario, we set B = 5 and randomly choose the parameters a i , d i , b i , R i , and there are 5 strategies indexed from 1 to 5, i.e., R = 5. We run the experiments in Scenario 2 including the following two settings: (1) • Our algorithms achieve at least 51% of the optimal utility in offline case, and 42% of the optimal utility in the online case.

d i -a i + 1 ≥ min r∈R i τ r,b i , and (2)
d i -a i + 1 ≥ l max + min r∈R i τ r,b i -1,
• By comparing the performance gains between the two settings, as the slackness of each request is relaxed, our algorithms in the second setting perform better compared to the first setting. • Our algorithms achieve at least 41% of the optimal utility in offline case, and 33% of the optimal utility in the online case.

• As in the first scenario, the smaller the number of strategies there is, the better performance our algorithms achieve.

Conclusion

In this chapter, we have formulated and analyzed the downlink transmission scheduling problem with data sharing. We have studied both offline and online scheduling scenarios. In both cases, we have established the problem hardness and developed deterministic approximation algorithms with mathematically proven performance guarantee. We have complemented our theoretical analysis with numerical simulations that demonstrate the effectiveness of our algorithms in a variety of system settings.

Appendix

Integer Linear Problem Formulation of Offline Downlink Transmission Scheduling

The offline downlink transmission scheduling with data sharing problem P3 can be formulated as a network utility maximization (NUM) problem as below.

P3: maximize

1≤i≤N r∈R i w i,r x i,r subject to t i -t j ≥ τ r j ,b j , ∀i, j ∈ N , t i > t j , r i = r j , x i,r i = x j,r j = 1. (4.4a) t i -t j ≥ τ r j ,b j , ∀i, j ∈ N , t i > t j , b i = b j , x i,r i = x j,r j = 1. (4.4b) t j > t i , ∀i, j ∈ N , β j > β i , x i,r i = x j,r j = 1. (4.4c) t j = t i , ∀j ∈ N , β j = β i , x j,r j = 1, i = min{k : x k,r k = 1, j ≥ k, k ∈ N b j , r k ∈ R j , a j ≤ t k ≤ d j -τ r k ,b j + 1}.
(4.4d)

a i ≤ t i ≤ d i -τ r i ,b i + 1, r i ∈ R i , x i,r i = 1, ∀i ∈ N . ( 4

Proof of Theorem 4.1

To prove its hardness, we consider the 0-1 Knapsack problem which is known to be NP-hard [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]. known to be NP-hard [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF].

We now show that the 0-1 Knapsack problem defined above, we construct an instance of P3 as follows: there are N users indexed from i = 1 to N , each submitting a request (0, T ), i.e., each request needs the whole time horizon; there is only one transmission strategy that can cover all users in the base station, where each user requests a distinguished packet; the time to transmit the packet requested by each user i is c i under the transmission strategy; the reward of each user i is c i ; as all requests are submitted at time 0, the service order is determined by user indexes. It is straightforward to see that a solution of the constructed instance of P3 can be cast to a solution of the 0-1 Knapsack problem.

It then follows from the NP-hardness of the 0-1 Knapsack problem that P3 is NPhard.

In the disctete case where all the parameters and variables are restricted to integers, we can apply the same procedure to cast the Knapsack problem with integer weights to the discrete downlink transmission scheduling problem. It then follows from the NPcompleteness of Knapsack problem with integer weights [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF] that the discrete version of P3 is also NP-complete.

Proof of Lemma 4.1

First, we prove that each IS of G maps to a feasible policy.

• The construction of type 1 edges ensures that the base station does not transmit multiple packets simultaneously.

• The construction of type 2 edges ensures that the priorities, under which the users are served, never violate our adapted FIFO model.

• The construction of type 3 edges ensures that for each user, at most one vertex covering it is chosen, i.e., each user is served at most once.

Therefore, each IS of G maps to a feasible policy.

We then prove the second property. Let N * denote the set of users that are served by an optimal feasible policy. Following our notation, we use a quadruple (i, t i , r i , β i ) to denote a request i served in N * , where t i denotes the starting time slot to serve request i, r i denotes the strategy under which the request i is served, and β i denotes the priority under which request i is served. We divide N * into subsets such that the requests belonging to the same subset are batched under the same priority. Let N * 0 denote the set of batch headers. Clearly, each request in N * belongs to a batch. It then follows from the optimality of N * that

N * = i∈N * 0 N + b i ,t i (i, r i ).
It follows from the feasible of N * that any pair of requests i, j ∈ N * 0 with i < j satisfies

t i + τ r i ,b i -1 < t j ≤ d j -τ r j ,b j + 1.
For each user i, a strategy r and a slot t, it follows from the definition of N + b i ,t (i, r) that the set of requests in

N + b i ,t (i, r) includes all requests k with k ≥ i, b k = b i that fit into the time interval [t, t + τ r,b i -1].
Consider any packet b and any pair of users i, j ∈ N * 0 with j < i requesting the packet b. We now prove that r j ∈ R \ R i when there exists a request in N + b,t i (i, r i ) that can fit into the time interval [t j , t j + τ r j ,b -1], i.e., N + b,t j (j, r j ) ∩ N + b,t i (i, r i ) = ∅. Assume by contradiction that r j ∈ R i when N + b,t j (j, r j ) ∩ N + b,t i (i, r i ) = ∅. For each request k ∈ N + b,t j (j, r j ) ∩ N + b,t i (i, r i ), it holds that i ≤ k and a i ≤ a k ≤ t j because of the definitions of N + b,t i (i, r i ) and N + b,t j (j, r j ). It then follows from r j ∈ R i and t j + τ r j ,b -1 < t i < d i that i fits into the time interval [t j , t j + τ r j ,b -1].

Based on the adapted FIFO model, request i must be batched with j or another request with higher priority than j. It then indicates that i is not a batch header, i.e., i / ∈ N * 0 , contradicting with i ∈ N * 0 , where the proof is completed. We then prove that there is a subset of vertices in V, which is an IS, covering all users in N * . Consider each packet b. For each request i ∈ N * 0 requesting the packet b, it follows from the construction of G that we can find a vertex in V, denoted by v * i , corresponding to the time interval [t i , t i + τ r i ,b i -1], the strategy r i , and the priority i.

The requests covered by v *

i is distinguished into two cases.

• If i has the highest priority among the users in

N * 0 requesting packet b, i.e., i = min k∈N * 0 ,b k =b k, then v * i covers requests N + b,t i (i, r i ).
• Otherwise, we select the request j = max k∈N * 0 ,k<i,b k =b k, if there is no user in N + b,t i (i, r i ) that can fit into the time interval [t j , t j + τ r j ,b j -1], i.e., N + b,t i (i, r i ) ∩ N + b,t j (j, r j ) = ∅, then v * i covers requests N + b,t i (i, r i ).

if there exists a user in N + b,t i (i, r i ) that can fit into the time interval [t j , t j + τ r j ,b j -1], i.e., N + b,t i (i, r i )∩N + b,t j (j, r j ) = ∅, then v * i covers requests N b,t i (i, i * ; r i , r j ), where i

* = max k∈N + b,t i (i,r i )∩N + b,t j (j,r j ) k. It holds that r j ∈ R \ R i .
We consider the set of vertices V * = {v * i } i∈N * 0 . It follows from the construction of vertices in V * that all requests in N * are covered by the vertices in V * , i.e.,

i∈N * 0 N (v * i ) = i∈N * 0 N + b i ,t i (i, r i ) = N *
, where N (v) denotes the set of requests covered by v.

Next, we prove that the set of vertices in V * is an IS of G. Consider any pair of vertices u, v ∈ V * with β u < β v . Since for any pair requests

k 1 , k 2 ∈ N * 0 with k 1 < k 2 it holds that t k 1 + τ r k 1 ,b k 1 -1 < t k 2 ,
the time intervals corresponding to u and v do not overlap, indicating that any pair of vertices in V * is not connected by the type 1 edge.

Based on the construction of the vertices in V * , we can derive that (1) t u < t v and ( 2)

N (u) ∩ N (v) = ∅,
indicating that any pair of vertices in V * is not connected by the type 2 edge and type 3 edge. the vertices in V α (k 2 ), all vertices u ∈ V α (k 1 ) \ V α (k 2 ) have been colored because of t u < min{t ν : ν ∈ V α (k 2 )}. Therefore, the colors that are used to the vertices in

V α (k 1 ) \ V α (k 2 ) can be used to the vertices in V α (k 2 ) \ V α (k 1 )
if there is also no type 1 and 3 edge. Hence, the number of colors that have been used to color the second class of neighbors is upper-bounded by ϕ l min • N -y * v N when Algorithm 3 colors v.

The third class of neighbors consist of the vertices that are connected with v by type-3 edges. Consider each request k covered by v. For each vertex u ∈ V k , the priority of u is higher than or equal to the priority of k, and the vertices in V k are valid at slot a k . It then follows from the definition of V α (k) that the vertices in V k are included by V α (k). We derive the number of colors that are occupied by the second class of neighbors based on that, for each request j ∈ N , the vertices in V α (j) are adjacent to each other. Therefore, the colors that have been used to the third class of neighbors are included by the colors already used to the second class of neighbors.

By combining the above analysis, the number of colors that have been used to the Let I denote the IS output by Algorithm 3. Since each vertex v ∈ V receives N y * v colors, we have

neighbors
v∈I * w v ≥ N |C| v∈V w v y * v - v∈V w v N > 1 1 + ϕ/l min OP T - RM δ RM δ 1+ max v∈V w v = 1 1 + ϕ/l min OP T - 1 δ max v∈V w v .
where the second inequality follows that the value of an optimal fractional LP solution is an upper bound on the value of an optimal feasible scheduling policy.

As it holds that max v∈V w v ≤ OP T , we then have

v∈I * w v > 1 1 + ϕ/l min (OP T - 1 δ • OP T ).
Noticing that asymptotically δ is sufficiently large, Theorem 4.2 is thus proved.

Proof of Theorem 4.4

Let O denote the set of requests that are served by the optimum scheduling policy.

We now prove that each request in O is ready at a slot in T . Consider each request k ∈ O. If a k ∈ T , clearly, the priorities to serve requests that start being served before slot a k is higher than the priority of request k. Therefore, request k is ready at slot a k , i.e., k ∈ Ω a k ; if a k / ∈ T , let t = max{t : t ∈ T , t < a k }, and let τ * denote the number of slots to serve the users in N * t . We prove that request k is ready at slot t + τ * and t + τ * ∈ T . We prove it in the following three steps.

• Step 1: We prove that t < a k < t+τ * . Assume by contradiction that a k ≥ t +τ * .

It follows from t = max{t : t ∈ T , t < a k } and a k / ∈ T that each slot in [t + τ * , a k ] is free when Algorithm 4 considers it. Because request k is ready at slot a k , Algorithm 4 starts serving at least one request at slot a k , i.e., a k ∈ T , contradicting with a k / ∈ T . It then holds that t < a k < t + τ * .

• Step 2: We prove that request k is ready at slot t + τ * . Since the slackness of each request i is at least l max + min r∈R i τ r,b i -1, we can derive that a k < t + τ * ≤ d k -min r∈R i τ r,b i + 1 because of t < a k < t + τ * and τ * ≤ l max . It also holds that starting serving request k at slot t + τ * does not violate the FIFO model because of a j ≤ t < a k and j < k for any j with t j < t + τ * . Therefore, request k is ready at slot t + τ * , i.e., k ∈ Ω t+τ * .

• Step 3: We prove that t + τ * ∈ T . Because requests in N * t are served completely at slot t + τ * -1, slot t + τ * is free when Algorithm 4 considers it. Therefore, Algorithm 4 starts serving at least one request at slot t + τ * since k is ready at slot t + τ * , i.e., t + τ * ∈ T .

Based on the above analysis, the total reward of the optimum scheduling policy can be upper-bounded by t∈T k∈Ωt w k , i.e., k∈O w k ≤ t∈T k∈Ωt w k .

Consider each slot t ∈ T . Because Algorithm 4 starts serving a set of users in Ω t , which request the same packet, with the maximum total reward among the packets in

B(Ω t ), the total reward of requests in Ω t is k∈Ωt w k ≤ |B(Ω t )| k∈N * t w k
Therefore, the total reward of the optimum scheduling policy can be upper-bounded by k∈O

w k ≤ t∈T k∈Ωt w k ≤ t∈T |B(Ω t )| k∈N * t w k ≤ B max • t∈T k∈N * t w k .
Theorem 4.4 is thus proved. in a variety of system settings.

Introduction

As an instantiation of our work, we consider the channel bonding problem in wireless networks. The proliferation of wireless mobile networks and the ever-increasing density of wireless devices underscore the necessity for efficient allocation and sharing of the radio spectrum resource. Spectrum bonding, or channel bonding, is widely regarded as an effective enabling technique that combines contiguous spectrum fragments to create a wideband channel for data transmission, thus significantly increasing the spectrum efficiency.

In this chapter, we focus on the design and analysis of spectrum bonding and the related transmission scheduling algorithms in dynamic spectrum access systems. Specifically, we study a generic scenario where a number of users can access a continuous frequency band; each user has a communication task and thus issues a request composed of the amount of contiguous bandwidth needed to accomplish the task and the duration of the task; admitted requests are served according to the FIFO model; non-interfering users may be allocated overlapping spectrum bands simultaneously. We are interested in designing spectrum bonding and the related scheduling algorithms maximizing the overall system utility.

The above algorithmic problem also arises in the context of dynamic storage allocation in computer systems, where a pool of continuous memory space is shared among a number of processes, each requesting to access a certain amount of contiguous memory for a certain amount of time; a request can be of type either read or write; multiple read requests may be served simultaneously, while a write request requires exclusive use of the requested memory; admitted requests are served according to the FIFO model. The central problem is to design memory allocation algorithms maximizing the aggregated system utility, e.g., maximizing the number of admitted requests.

The above two examples further push us to formulate a generic task scheduling problem, where a set of independent tasks need to be executed on a pool of continuous resource, each requiring a certain amount of time and certain amount of contiguous resource. Some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource. Tasks are served in the FIFO manner. We seek an optimal resource allocation and scheduling policy maximizing the overall system utility.

In this chapter, we embark on an algorithmic study of the above contiguous-resource batching task scheduling problem by instantiating our analysis in the context of spectrum bonding for the sake of concreteness. We investigate both offline and online scheduling settings. In both cases, we develop approximation algorithms with proven performance guarantee in terms of approximation and competitive ratios, respectively.

Technically, we first demonstrate the hardness of our problem by showing that (1) the offline problem is NP-hard, (2) the online problem in its generic form cannot be approximated with any finite competitive ratio. Given the hardness of both the offline and online problems, we then seek approximation algorithms. In the offline problem, we develop an algorithmic framework by mapping the problem to a particular variant of the MWIS problem, termed as maximum weighted regular independent set (MWRIS), by integrating the specific constraints posed by our problem; we then solve the LP relaxation of MWRIS problem; we further develop a coloring-based algorithm that rounds the solution of the LP relaxation to an integer solution and establish its performance bound. In the online problem, we develop an iterative algorithm that greedily selects the most profitable tasks and prove that, as long as each task has certain slackness (cf. Section 5.4 for details), our algorithm can achieve finite competitive ratio.

The rest of this chapter is organized as follows. Section 5.2 formulates the contiguousresource batching task scheduling problem. Section 5.3 analyzes the offline setting and develops the scheduling algorithmic framework. Section 5.4 studies the online setting and presents the design of an online scheduling algorithm. Section 5.5 presents the simulation results demonstrating the efficiency of our proposed algorithms. Section 5.6 concludes the chapter.

System Model

For the sake of concreteness, we present the system model of our problem in the context of channel bonding. Nevertheless, as explained in the Introduction, the model can be readily applied in a variety of task scheduling scenarios where a pool of resource needs to be allocated to a set of tasks following the FIFO model, some of which can be served together on common resource. Therefore, the following description and the use of terms such as frequency band, user, transmission, etc., should be understood generically.

We consider a dynamic spectrum access system where a set N of N users can access a common frequency band. We focus on the discrete case where both time and frequency bands are discretized. To make our analysis concise without losing generality, we assume that time is divided to unit-length slots from 0 to T and the available frequency band, aka white space, is normalized to [0, F ] with the finest frequency granularity being 1.

Each user i submits its bandwidth request in the form of a quadruple (a i , d i , f i , l i ), where a i denotes the arrival time of the request at the spectrum broker that manages the spectrum resource, d i denotes the deadline before which the request needs to be satisfied if admitted by the broker, f i is the quantity of contiguous frequency band requested, l i is the number of slots the user requests to use the spectrum, (d i -a i + 1) is the slackness of the user i. In other words, if the spectrum broker decides to serve request i, it needs to reserve f i amount of contiguous frequency band to user i for l i contiguous slots in the time interval [a i , d i ], as illustrated in Figure 5.1. We associate a reward w i for each request i. 5.1 lists the main notations used in the chapter.

In the above generic model, we are interested in both offline and online optimal spectrum bonding and scheduling policies for the spectrum broker to maximize the total reward. Both policies follow the FIFO service model such that admitted requests are queued at the broker in the same order they arrive and a request is cleared when the corresponding user is served. Without loss of generality, we assume that a i ≤ a j for any 1 ≤ i < j ≤ N ; in case where a i = a j and i < j, request i should be served first.

v ∈ V + i N b set of requests in N belonging to group b F b max k∈N b f k f b min k∈N b f k L b max k∈N b l k l b min k∈N b l k f min min k∈N f k f max max k∈N f k l min min k∈N l k l max max k∈N l k R max 1≤b≤B (F b -f b + 1)(L b -l b + 1) M max 1≤b≤B |N b | δ i∈N (d i -a i -l i + 2) y v
binary variable indicating whether or not vertex v is selected in the IS is assigned a priority level i. For each elementary vertex v of request i, let N + v denote the set of requests k > i, i.e., with lower priority, that can be served together with i by reusing the time-frequency block of v, i.e.,

N + v {k : k > i, k ∈ N b i , l k ≤ l i , f k ≤ f i , t v + l i -l k ≥ a k , d k -t v + 1 ≥ l k }.
Induced vertices. Consider each elementary vertex v of each request i. For each request j ∈ N + v , we create an induced vertex u for each rectangle of height f j and length l j in the rectangle [s v , s v + f i -1] × [max{t v , a j }, max{t v , a j } + l i -1], and assign u to j. We set the priority of u to i. We say that u reuses the time-frequency block corresponding to v. We define u as a child of v, and inversely v as the parent of u, denoted by v ≺ u. We note that an elementary vertex may have multiple children, while an induced vertex has only one parent.

We denote V i the set of the elementary vertices of request i plus the induced vertices assigned to i. For each vertex v ∈ V i , we say that v covers i. We define a weight w v for v and set w v = w i . Let β v denote the priority of vertex v. Mathematically, a smaller β indicates a higher priority. 5.2. The unique optimal scheduling policy, starting serving requests 1 and 3 under the priority

• For each pair of elementary vertices v ∈ V + i and u ∈ V + j , we construct an edge between v and u if i > j and t v < t u or i < j and t v > t u , indicating that their corresponding requests cannot be both instantiated by u and v under the adapted FIFO model.

• For any pair of elementary vertices v ∈ V + i and u ∈ V + j satisfying j ∈ N + v and t v ≤ t u , we construct an edge between them. The implication of this class of edges is below. Suppose request i is instantiated by v. It follows from j ∈ N + v that request j can fit into the service time of i and the spectrum allocated to i.

It then follows from the adapted FIFO model that if request j is served, it must be batched with i or another request with higher priority than i. Hence, i and j cannot be both instantiated by v and u.

Type-3: intra-user edges. For each request i ∈ N , we construct an edge between each pair of vertices in V i . The intra-user edges model the constraint that any user is served at most once.

We now analyze the complexity of creating the edges in G. As the number of elementary vertices in G is O((F -f min )δ), the construction of type 1 and 2 edges can be completed in O((F -f min ) 2 δ 2 ), asymptotically O(F 2 δ 2 ), time. For each request i, there are at most RM (F -f i +1)δ i vertices in V i . Therefore, the construction of type 3 edges takes

O i∈N δ 2 i (F -f min ) 2 R 2 M 2 + F 2 δ 2 , asymptotically O F 2 R 2 M 2 i∈N δ 2 i , time.
Example 5.3. where y v is the binary variable indicating whether vertex v is selected. Constraint (5.1) states that any pair of neighboring vertices cannot be chosen together. Constraint (5.2) states that an induced vertex can be chosen if and only if its parent is chosen.

LP Relaxation

To solve the MWRIS problem formulated above, we first solve its linear programming (LP) relaxation and then round the LP solution to a RIS. In this subsection we develop an LP relaxation approach tailored to our problem. The next subsection is devoted to the rounding process. (l max -l min + 1) 2 (f max -f min + 1)

• F f min • λ-l min +lmax l min D 2 max 1≤b≤B (L b + l b )(L b -l b + 1)(F b -f b + 2)/2 N (F -f min + 1)δ 1+ V
set of auxiliary vertices generated from the vertices in V C ordered set of (D

1 + f max • D 2 ) N -f max colors Γ v
set of vertices including v to be colored in the iteration of coloring v Γ * set of vertices from which the vertices in Γ are generated V k,v set of vertices generated from the vertices u ∈ V k with v ≺ u,

for each elementary v ∈ V, each request k ∈ N + v
In the LP relaxation, for each vertex v ∈ V, we replace the constraint y v ∈ {0, 1} by y v ≥ 0. There is no need to explicitly add the constraint y v ≤ 1 since it is implied by the other constraints. We add the constraint v∈V i y v ≤ 1 to restrict that each request i is served at most once. For each elementary vertex v, we replace constraint (5.2) by group b with t v ≥ a i is upper-bounded by (l max -l min + 1)(f max -f min + 1) at any feasible scheduling policy. By combining the above analysis, the number of vertices in V c (i) belonging to group b is upper-bounded as (l max -l min + 1) 2 (f max -f min + 1) at any feasible scheduling policy.

Let λ max k∈N (d k -a k + 1). Because the spectrum allocated to any pair of requests belonging to different groups cannot overlap, the requests in N c (i) that are served by allocating the time-frequency blocks in the spectrum [max{0, a i + l min -

l max }, max k∈N c (i) d k ] × [0, F ] are from at most F f min • max k∈N c (i) d k -a i -l min +lmax+1 l min ≤ F f min • λ-l min +lmax
l min groups at any feasible scheduling policy, indicating the following constraints.

Type-2 constraints:

v∈V c (i) y v ≤ D 1 , ∀i ∈ N , (5.5)
where

D 1 = (l max -l min + 1) 2 (f max -f min + 1) • F f min • λ-l min +lmax l min .
We now derive the complexity to establish type-2 constraints. For each user i, there

v∈V i y v ≤ 1, ∀i ∈ N y v ≥ 0, ∀v ∈ V
We do not have to explicitly add the constraint y v ≤ 1 since it is implied by the other constraints. We have shown that any feasible scheduling policy is a feasible solution of P4'. Hence, the value of an optimal fractional solution of P4' is an upper bound of the feasible scheduling policy.

Approximation Scheduling Algorithm

Our approximation scheduling algorithm first solves P4', then applies the rounding and coloring technique developed in [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF] adapted to our context. To make our presentation streamlined and self-contained, we present and analyze the adapted rounding algorithm in the context of our problem. At a high level, our algorithm constructs a set of auxiliary vertices based on the rounded solution of P4' and then colors the auxiliary vertices such that each color induces a RIS. We further adjust the optimal RIS among the constructed RISes such that the set of resulting vertices still forms a RIS and thus maps to a feasible scheduling policy. The algorithm is composed of three steps, which are exposed sequentially. The first two steps essentially follow the procedures in [START_REF] Bar-Noy | Approximating the throughput of multiple machines in real-time scheduling[END_REF],

which are adapted below in the context of our problem. In the third step, we adjust the RIS such that the vertex set still forms a RIS and maps to a feasible scheduling policy.

Some additional notations are used in this subsection. Let

D 2 max 1≤b≤B (L b + l b )(L b -l b + 1)(F b -f b + 2)/2. Let N (F -f min + 1)δ 1+ .
To make our analysis concise, we assume that N is an integer, otherwise we need to round it to the nearest integer. Let f max max k∈N f k , and let C denote an ordered set (or a vector) of

(D 1 + f max • D 2 ) N -f max colors.
Step 1: Generating the auxiliary vertices. We solve P4' and denote the solution by {y * v } v∈V . Clearly, we have 0 ≤ y * v ≤ 1, ∀v ∈ V. For each vertex v ∈ V, we create a set of y * v N new vertices, termed as auxiliary vertices. Each generated vertex is a duplicate of v, corresponding to the same rectangle, having the same priority and covering the same request as v. Let V denote the set of auxiliary vertices generated from V. For each elementary v ∈ V and each request k ∈ N + v , let V k,v denote the set of auxiliary vertices in V generated from the induced vertices u ∈ V k with v ≺ u. We say that the vertices in V k,v are the auxiliary children of v covering request k.

Step 2: Coloring the auxiliary vertices. We color each vertex in V by a color such that (1) any pair of vertices generated from a same vertex in V is not of the same color; (2) any pair of vertices that are generated from the adjacent vertices in V is not of the same color; and (3) an induced vertex has the same color as an elementary vertex that is generated from its parent. Specifically, we first sort the elementary vertices in V such that for any pair of elementary vertices u, v ∈ V , v is left to u if t v < t u or t v = t u , s v < s u , with ties broken randomly. Step 2 is then executed in iterations. In each iteration, we try to color an elementary vertex in V . For each elementary vertex u ∈ V from left to right, we stock the set of vertices to be colored in the current iteration in Γ, which is initialized to {u}. Let v denote the vertex in V from which u is generated. If N + v = ∅, for each request k ∈ N + v , if there is an uncolored induced vertex in V k,v , we add the vertex to Γ. We finalize the coloring process of the elementary vertex u by coloring all vertices in Γ using the first color in C that has not been used to color any vertex generated from the vertices in Γ * and the neighbors of Γ * , where Γ * stocks the set of vertices in V from which the vertices in Γ are generated.

Step 3: Adjusting the RIS. Based on the coloring result obtained in Step 2, we choose a set of vertices of the same color with maximum total weight, and let V denote the set of vertices in V from which the chosen vertices are generated. We prove that the set of vertices, from which the vertices of the same color are generated, is a RIS in Lemma 5.5. However, V may not map to a feasible policy. In this case, we adjust V such that it forms a RIS and maps to a feasible scheduling policy. Consider a RIS mapping to a feasible scheduling policy. For each vertex u in the RIS, let i denote the request covered by u. Based on the definition of the adapted FIFO model, u uses or reuses the time-frequency block of the vertex with highest priority among u and the elementary vertices v in the RIS with i ∈ N + v . Technically, for each vertex ν ∈ V, let k denote the request covered by ν. If ν is an elementary vertex, we prove that there is no elementary vertex v ∈ V with β v < β ν and k ∈ N + v in Lemma 5.6. If ν is an induced vertex, we first seek the set of elementary vertices v ∈ V with k ∈ N + v , and denote the set of vertices by Φ. Since V is a RIS, the parent of ν also belongs to Φ. We then pick the vertex with highest priority among the vertices in Φ, denoted by µ. Because the parent of ν belongs to Φ and µ has the highest priority among the vertices in Φ, the priority of µ is higher than or equal to that of ν, i.e., β µ ≤ β ν . If β µ = β ν , request k is instantiated by ν by reusing the time-frequency block of µ; if β µ < β ν , request k should be served by reusing the time-frequency block of µ under the priority of µ, and we thus replace ν by an induced vertex in V k whose parent is µ in V. It follows from the construction of vertices in G that there is at least one induced vertex in V k whose parent is µ as k ∈ N + µ .

Example 5.4. We illustrate Step 3 by reconsidering Example 5.2, where we select V = {v 1 , v 3 , v 8 , v 12 , v 13 }. It can be noted that V is a RIS of G but does not map to a feasible scheduling policy, we replace v 8 by v 4 in V. Now V maps to the unique optimal scheduling policy.

We summarize that the key technicality in our algorithm is to color each induced vertex using the same color as its parent, and then adjust the RIS to obtain a feasible scheduling policy.

The pseudo-code of our algorithm is given in Algorithm 5. As each vertex corresponds to a request, the final scheduling policy is to serve the requests corresponding to the set of vertices output by Algorithm 5. In the following, we briefly describe the functions used in our algorithm, most of which are graph algorithms that can be coded straightforwardly. The detailed implementation is thus omitted in the pseudo-code.

• AuxiliaryChildren(v, k, V ) returns the set of auxiliary vertices in V generated from the induced vertices in V k whose parents are v, given the elementary vertex v ∈ V, the request k ∈ N + v and the set of auxiliary vertices V .

• SimultaneousColoredVertex(V k,v ) returns an uncolored vertex in V k,v if such vertex exists, ∅ otherwise, given the set of vertices V k,v .

• GeneratedfromVertices(V * , V) returns the set of vertices in V, from which the vertices in V * are generated, given the sets of vertices in V and V * ⊆ V .

• UsedColors(Γ * ) returns the set of colors that have been used to the colored vertices generated from the vertices in Γ * and the neighbors of Γ * , given the sets of vertices in Γ * .

• Color(C * , C) returns the first color in C \ C * , given the sets of colors in C and C * .

• MaxWeightVertices(V ) returns the set of vertices in V of the same color with maximum total weight, given the set of vertices in V .

• FittedVertices(i, V) returns the set of elementary vertices v ∈ V with i ∈ N + v , given the request i, and the set of vertices in V.

• HighestPrioVertex(Φ) returns the vertex with the highest priority among the vertices in Φ, given the set of vertices in Φ.

• InducedVertex(µ, V i ) returns an induced vertex in V i whose parent is µ, given the elementary vertex v and the set of vertices in V i .

Algorithm 5 Offline scheduling policy: executed by the scheduler

1: Input: request graph G = (V, E), solution of the LP relaxation {y * v } v∈V , N = (F -f min + 1)δ 1+ , a vector C of (D 1 + f max • D 2 ) N -f max colors 2: Output: set of vertices V
The corresponding policy is to serve the requests corresponding to V 3: V ← ∅ V stocks the set of auxiliary vertices generated from V Theorem 5.2 demonstrates that the approximation factor of our algorithm depends on the largest request slackness and parameters l b , L b , f b , F b , l max , l min , f max , f min , F , where F is a constant. Thus, the performance does not degrade with the system size.

We conclude the analysis by giving the complexity of our approximation algorithm.

We first need to compute the number of vertices in V . To that end, we can calculate the number of created vertices in V that is O(RM F δ). The total number of vertices in V sums to |V | = O(RM F δ N ). The complexity for the sorting of the elementary vertices in V is O(F δ N log(F δ N )) since there are at most F δ N elementary vertices in

V . Therefore, it follows from N = (F -f min +1)δ 1+ that the complexity of Algorithm 5

is O(RM F 2 δ 2+ + F 2 δ 2+ log(F δ)).

The Online Case

In this section, we consider the online scheduling problem, where the scheduler only knows the current scheduling backlog. More specifically, a i , d i , f i , l i , b i , and w i are known only at the moment when request i arrives. As the offline case, the online scheduling problem also takes into account the adapted FIFO service model and the spectrum reusability. Table 5.4 lists the additional notations in the online setting. The pseudo-code of our online algorithm is given in Algorithm 6. Consider each slot t where there exists at least one ready request, i.e., Ω t = ∅, we proceed by distinguishing the following two cases.

• Slot t is occupied. For each request j ∈ Ω t , if there is at least one request k ∈ N - t of group b j such that j fits into the time-frequency block [t,

t k + l k -1] × [s k , s k + f k -1],
we pick the request with highest priority among the requests, denoted by i; we serve j by reusing the time-frequency block of i under the priority of i.

• Slot t is not occupied. Algorithm 6 runs in iterations. In each iteration, we try to start serving the requests in Ω t belonging to a same group at slot t. Let f * denote the amount of spectrum already occupied by the requests that start being served at the current slot. We first pick the group such that the total reward of the requests k ∈ Ω t with f k ≤ F -f * + 1 of group b is maximum among all the groups in B(Ω t ). We denote the selected group by b. Mathematically,

b = argmax b∈B(Ωt) k∈Ωt,b k =b,f k ≤F -f * +1 w k .
We then serve the requests k ∈ Ω t of group b with f k ≤ F -f * + 1 in rounds. In each round, we first pick the request i of the highest priority among the requests

k ∈ Ω t with f k ≤ F -f * + 1 of group b, i.e., i = min k∈Ωt,b k =b,f k ≤F -f * +1 k. We serve each request k ∈ Ω t of group b with l k ≤ l i , f k ≤ f i by allocating the time-frequency block [t, t + l k -1] × [f * , f * + f k -1]
under the priority of i, and remove k from Ω t . We continue starting serving requests of group b at slot t until there is no request k ∈ Ω t of group b satisfying f k ≤ F -f * + 1.

We briefly describe the following functions used in our algorithm, which can be coded straightforwardly. The detailed implementation is thus omitted in the pseudo-code.

• FittedRequests(i, N - t ) returns the set of requests k ∈ N - t of group b i such that i fits into the time-frequency block [t,

t k + l k -1] × [s k , s k + f k -1] if such requests
exist, and ∅ otherwise, given the request i and the set of requests N - t .

• HighestPrioRequest(Φ) returns the highest priority request in Φ, given the set of requests in Φ.

• MaxRewardGroup(Ω t , f * ) returns the group such that the set of requests k ∈ Ω t of the group with f k ≤ F -f * + 1 has the maximum total reward among the groups in B(Ω t ), given the set of requests Ω t , and the amount of spectrum f * already occupied by the requests that start being served at the current slot.

Algorithm 6 Online scheduling policy: executed by the scheduler at each slot t

i -1] × [s i , s i + f i -1] under the priority of β i 3: Initialization: f * = 0, N * t ← ∅ 4: if Ω t == ∅ then 5: return ∅ 6: end if 7: if slot t is occupied then 8: for each request k ∈ Ω t do 9: Ψ ← FittedRequests(k, N - t ) 10: if Ψ = ∅ then 11:
i ← HighestPrioRequest(Ψ)

12:

t k = t, s k = f i , β k = i
Request k is served by reusing the time-frequency block of i is ready at a slot in T . For each slot t ∈ T , we then derive the relationship between the total reward of the requests starting being served by Algorithm 6 at slot t and the total reward of the requests ready at slot t. Combining the above results allows us to establish the competitive ratio upper-bound of Algorithm 6. Theorem 5.4 shows that the performance of our algorithm only scales with the largest size of B(Ω t ), which only depends on the number of packets that are requested by the ready users at the current slot t. Therefore, the global efficiency of our algorithm does not degrade with the system size.

Numerical Analysis

In this section, we conduct numerical analysis to evaluate the performance of the offline and online scheduling algorithms we develop. In our simulation, we trace the metric (3.8) to evaluate the performance of the optimal scheduling policy compared to our algorithms. Specifically, we trace the maximal, average, and minimal values of Υ in our simulations.

The time horizon T is set to 200, the amount of frequency granularity F is set to 10; l max = 10, l min = 1. We simulate three typical scenarios, in each of which we vary the number of requests N in the system from 50 to 500. For each N , we perform 50 simulation runs for each request parameter setting.

Scenario 1

In the first scenario, we randomly choose the parameters a From the simulation results, we make the following observations.

i , d i , f i , l i , b i such that 1 ≤ f i ≤ F, d i -a i + 1 ≥ l i ,
• Our algorithms achieve at least 44% of the optimal utility even in the worst case in the offline setting and at least 30% in the online setting, which are in accordance to the theoretical results we derive.

• Our offline algorithm performs better compared to our online algorithm, as the spectrum broker disposes more information in the offline setting and naturally achieves better performance. • When the number of requests N increases, the average and minimum performance gains first decrease in both offline and online cases, and then stabilize, indicating that the resource pool approaches its capacity limit.

• The smaller the number of groups there is, the better performance our algorithms achieve. This is because, when the number of groups is small, there are more opportunities for spectrum reuse, which potentially improves the system performance.

Scenario 2

In this scenario, we set B = 5 and randomly choose the parameters a

i , d i , f i , l i , b i such that d i -a i + 1 ≤ l i , ∀i ∈ N .
The experiments of Scenario 2 include the following two settings: (1) 1 ≤ f i ≤ F, ∀i ∈ N , and (2) f i = F, ∀i ∈ N , i.e., each user requests the whole frequency band. The simulation results of this scenario are illustrated in Figures 5.7 and 5.8. From the results, we make the following observations.

• Our algorithms achieve at least 47% of the optimal utility in offline case, and 38% of the optimal utility in online case. • By comparing the performance gains between the two settings, as the slackness of each request is relaxed, our algorithms in the second setting perform better compared to the first setting.

Conclusion and Perspective

Motivated by the spectrum bonding problem, we have formulated and analyzed the contiguous-resource batching task scheduling problem arising in a variety of engineering fields, where communication and storage resources are potential bottlenecks and thus need to be carefully scheduled. We have investigated both offline and online scheduling settings. In both cases, we have established the problem hardness and developed approximation algorithms with proven performance guarantee in terms of approximation and competitive ratios, respectively. We have complemented our theoretical analysis with numerical simulations that demonstrate the effectiveness of our algorithms in a variety of system settings.

(i ∈ {1, 2, • • • , N }), find a set N ⊆ {1, 2, • • • , N } such that i∈ N c i ≤ C and i∈ N w i is maximized.
The problem is known to be NP-hard.

We now show that the 0-1 Knapsack problem can be reduced to P4. To this end, consider an instance of the 0-1 Knapsack problem defined above, we construct an instance of P4 as follows: there are N users indexed from i = 1 to N , each submitting a request (0, T, F, c i ), i.e., each request i needs the whole spectrum, the required service time is c i ; no spectrum reuse is possible; as all requests are submitted at time 0, the service order is determined by user indexes; the reward of each request i is w i . It is straightforward to see that a solution of the constructed instance of P4 can be cast to a solution of the 0-1 Knapsack problem.

It then follows from the NP-hardness of the 0-1 Knapsack problem that P4 is NPhard.

In the discrete case where all the parameters and variables are restricted to integers, we can apply the same procedure to cast the Knapsack problem with integer weights to the discrete channel bonding problem. It then follows from the NP-completeness of Knapsack problem with integer weights [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF] that the discrete version of P4 is also NP-complete.

Proof of Lemma 5.1

Consider any feasible scheduling policy mapping to a subset of vertices in V. We first prove that the subset of vertices is an IS of G. Assume by contradiction that to a same group. Assume by contradiction that for a (t, s) pair, there is a pair of vertices u, v ∈ V α (t, s) belonging to different groups at a feasible scheduling policy.

It follows from the construction of G that u and v are connected by a type 1 edge.

This contradicts to the fact that any feasible scheduling policy maps to a RIS of G.

Therefore, for each (t, s) pair, the size of V α (t, s) at any feasible scheduling policy is upper-bounded by max b∈B α (t,s)

(L b + l b )(L b -l b + 1)(F b -f b + 1)/2.

Proof of Lemma 5.3

Consider each group b ∈ B c (i) and each slot τ ≥ max{0,

a i + l min -l max }. Let V c τ (i) denote the set of elementary vertices v ∈ V c (i) with t v = τ . Let N c τ (i) denote the set of requests having at least one vertex in V c τ (i). It follows from the definition of V c τ (i) and N c τ (i) that max k∈N c τ (i) a k ≤ τ . • For each slot τ ∈ [max{0, a i + l min -l max }, a i ), because t v = τ, ∀v ∈ V c τ (i) and max k∈N c τ (i) a k ≤ τ , i.e., t v ≥ max k∈N c τ (i) a k , ∀v ∈ V c τ (i)
, it follows from Lemma 5.7 that for each (l, f ) pair, where l ∈ [l min , l max ] and f ∈ [f min , f max ], there is at most one vertex u ∈ V τ (i) at any feasible scheduling policy with l u = l and h u = f . It then follows from l ∈ [l min , l max ] and f ∈ [f min , f max ] that the size of V c τ (i) at any feasible scheduling policy is upper-bounded by (l max -l min + 1)(f max -f min + 1). Therefore, the size of t∈[max{0,a i +l min -lmax},a i ) V c t (i) at any feasible scheduling policy is upper-bounded by (l max -l min + 1)(f max -f min + 1)(l max -l min ).

• For the slots τ ≥ a i , it follows from the definition of V c (i) that the arrival time of any request having a vertex in V c (i) is no later than slot a i . It then follows

from τ ≥a i V c τ (i) ⊆ V c (i) that a k ≤ a i , ∀k ∈ τ ≥a i N c τ (i). Because of t v ≥ a i , ∀v ∈ V c
τ (i), it follows from Lemma 5.7 that for each (l, f ) pair, where l ∈ [l min , l max ] and f ∈ [f min , f max ], there is at most one vertex u in τ ≥a i V c τ (i) at any feasible scheduling policy with l u = l and h u = f . Therefore, the size of τ ≥a i V c τ (i) at any feasible scheduling policy is upper-bounded by (l max -l min + 1)(f max -f min + 1). By combining the above analysis, for each group b and each request i ∈ N b , there are at most (l max -l min +1) 2 (f max -f min +1) elementary vertices in τ ≥max{0,a i +l min -lmax} V c τ (i) at any feasible scheduling policy. Thus, it then follows from V c (i) = τ ≥max{0,a i +l min -lmax} V c τ (i) that the size of elementary vertices in V c (i) at any feasible scheduling policy is upperbounded by (l max -l min + 1) 2 (f max -f min + 1).

It then follows from Algorithm 5 and Lemma 5.8 that all elementary vertices in V are colored.

We now prove that all induced vertices are also colored by Algorithm 5. Because each induced vertex in V has only one parent, we just need to prove that for each elementary vertex v ∈ V and each request k ∈ N + v , when the vertices generated from v are colored, all vertices generated from the induced vertices in V k whose parents are v are also colored.

Consider each elementary vertex v ∈ V and each request k ∈ N + v . It follows from the constraint (5.3) that

ν∈V k ,v≺ν y * ν N ≤ y * v N .
Thus, the number of vertices in V k,v is upper-bounded by the number of vertices generated from v. When Algorithm 5 colors an vertex v generated from v, it follows from

Step 2 of Algorithm 5 that there is a vertex in V k,v is also colored using the same color as v if there is at least one uncolored vertex in V k,v . Therefore, when all elementary vertices generated from v are colored, all induced vertices in V k,v are also colored. By combining the above analysis, it holds that all vertices in V are colored by Algorithm 5. Lemma 5.4 is thus proved.

Proof of Lemma 5.5

We first prove that the set vertices, from which the vertices colored by c are generated, is not adjacent to each other. For any elementary vertex v ∈ V colored by c, there is only one elementary vertex in Γ v , and no two of vertices cover a same request.

Based on the construction of G, any pair of vertices in Γ * v is not adjacent to each other. It follows from Algorithm 5 that c is not used to color any other vertex generated from Γ * v and the neighbors of Γ * v . Therefore, any pair of vertices colored by c is not generated from a same vertex and any pair of adjacent vertices, indicating that the set of vertices, from which the vertices colored by c are generated, satisfies the first property of RIS.

For any induced vertex u ∈ V colored by the color c, let u denote the vertex from which u is generated. By the proof of Lemma 5.4, their is a vertex, which is generated from the parent of u, colored by c, indicating that the set of vertices, from which the vertices colored by c are generated, satisfies the second property for RIS of G.

By combining the above analysis, it holds that the set of vertices, from which the vertices colored by c are generated, induces a RIS. Lemma 5.5 is thus proved.

Proof of Lemma 5.6

It follows from Lemma 5.5 that the set of vertices, denoted by V, output by Algorithm 5 is a RIS. For each vertex v ∈ V, let i denote the user corresponding to v.

• Case 1: v is an elementary vertex. There is no elementary vertex u ∈ V belonging to group b i with β u < β v such that i can fit into the time-frequency block of u. Assume, by contradiction, that there is an elementary vertex u ∈ V of group b i with β u < β v whose corresponding time-frequency block fits for serving i. If t u > t v , u and v are connected by a type 2 edge because of β u < β v ; if t u ≤ t v , u and v are connected by a type 2 edge because i fits into the time-frequency block of u, i.e., i ∈ N + u . In both case, u and v are connected by an edge, contradicting to the fact that V is a RIS.

• Case 2: v is an induced vertex. There is no elementary vertex u ∈ V belonging to the same group as i with β u < β v such that i can fit into the time-frequency block of u; otherwise, it follows from Step 3 that v has been replaced by an induced vertex in V i whose parent has the highest priority among the elementary vertices µ ∈ V belonging to group b i with i ∈ N + µ .

Therefore, the set of vertices output by Algorithm 5 maps to a feasible scheduling policy. we then have

v∈I * w v > 1 A (OP T - 1 δ • OP T ),
The theorem is thus proved.

Proof of Theorem 5.4

For a slot t ∈ T . Let O denote the set of requests that are served by the optimum scheduling policy.

We now prove that each request in O is ready at a slot in T . Consider each request k ∈ O. If a k ∈ T , it follows from the definition of ready request that k is ready at slot a k , i.e., k ∈ Ω a k ; if a k / ∈ T , let t = max{τ : τ ∈ T , τ < a k } and l * = max k∈N * t l k . We prove that request k is ready at slot t + l * and t + l * ∈ T . We prove it in the following three steps.

• Step 1: We prove that t < a k < t+l * . Assume, by contradiction, that a k ≥ t+l * .

It follows from t = max{τ : τ ∈ T , τ < a k } and a k / ∈ T that each slot in [t + l * , a k ] is not occupied when Algorithm 6 considers it. Because request k is ready at slot a k , Algorithm 6 starts serving at least one request at slot a k , i.e., a k ∈ T , contradicting with a k / ∈ T . It then holds that t < a k < t + l * .

• Step 2: We prove that request k is ready at slot t + l * . Since the slackness for each request i is at least l max + l i -1, we can derive that a k < t + l * ≤ d k -l k + 1 because of t < a k < t+l * and l * ≤ l max . It also holds that starting serving request k at slot t + l * does not violate the FIFO model because of a j ≤ t, ∀j ∈ N * t and a k > t. Therefore, request k is ready at slot t + l * , i.e., k ∈ Ω t+l * .

Step 3: We prove that t+l * ∈ T . Because requests in N * t are served completely at slot t + l * -1, slot t + l * is not occupied when Algorithm 6 considers it. Therefore, Algorithm 6 starts serving at least one request at slot t + l * since request k is ready at slot t + l * , i.e., t + l * ∈ T .

Based on the above analysis, we can derive that the total reward of the optimum scheduling policy can be upper-bounded by This thesis has dedicated to the fundamental batching task scheduling problems, each of which has its own particularities and calls for specific analysis that cannot draw upon existing results, at the theoretical modeling and analysis and the approximation algorithm design, with Chapter 2 reviewing the related literature, Chapter 3 focusing on developing an algorithmic framework for the baseline scenario of batching task scheduling problem, Chapters 4 and 5 presenting approximation algorithms in both offline and online settings with mathematically proven performance guarantee for the problems of downlink transmission scheduling with data sharing and contiguous-resource batching task scheduling, respectively. More specifically, Chapter 3 has developed an algorithmic framework achieving 1/2-optimality for the baseline scenario of batching task scheduling problem, outperforming the best known result, and derived the first deterministic approximation algorithm outputting a l min /(2(l min + 1))-optimal scheduling policy for the generalized proportional broadcast problem by applying our algorithmic framework to the problem. In Chapters 4 and 5, we have formulated and analyzed the downlink transmission scheduling with data sharing and contiguous-resource batching task scheduling problems, which significantly generalize the baseline scenario of batching task scheduling problem, respectively, and we have studied the problems in both offline and online cases by establishing the problem hardness and developing deterministic approximation algorithms with mathematically proven performance guarantee. We have conducted numeric experiments under a variety of typical parameter settings to demonstrate the effectiveness of our algorithms for the above problems.

By summarizing the previous problems, the core technicality in our design is an LP 123 relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a feasible scheduling policy in offline case. In the online case, at each slot, at which no request or task is being executed, our online algorithms start serving a set of users requesting the same packet or belonging the same group such that the total reward of the users is maximum.

Open Questions and Future Work

In this section, we develop the discussion on open issues and questions and future work. The first is to extend the problems we address in Chapters 4 and 5 to the setting of multiple resource pools, where each task is to be scheduled in one of them, thus adding another dimension to the problems. Note that our algorithmic framework can be easily extended to the setting of multiple resources. The second and third future directions we expect to look into are to study dependent batching task scheduling and to concern flexible FIFO model in the problems of downlink transmission scheduling with data sharing and contiguous-resource batching task scheduling.

Dependent batching task scheduling

Throughout the full text, the tasks in the problems we address are independent. We expect to look into a generic task scheduling problem: a set of interdependent tasks need to be executed, each associated with a time window and, if admitted, needs to be executed within the window by exclusively using the resource; some tasks can be executed simultaneously by sharing the resource, while others require exclusive use of resource. The dependency among tasks forms a directed acyclic graph such that each task can be executed iff all the tasks preceding it are completely executed. The goal is to seek an optimum scheduling algorithm maximizing the overall system utility. The above scheduling problem arises in a variety of engineering fields where computing, communication, and storage resources are potential bottleneck and thus need to be carefully scheduled.

Despite its theoretical and practical importance, the problem of scheduling interdependent batching tasks is still a largely unexplored area, where the challenges brought by task dependency and batching execution need to be addressed holistically in the design of scheduling algorithms maximizing the system overall utility. Thus, we expect that the problems not only consider task batching, i.e., some tasks can be executed Abstract: In this thesis we formulate and analyze a class of fundamental task scheduling problems arising from a variety of emerging computing and communication systems: tasks are partitioned into groups; those in a group can be batched and executed simultaneously; the goal faced by the scheduler is to design scheduling algorithms maximizing the overall system utility. Under the above generic umbrella, we investigate different classes of batching task scheduling problems, establishing the corresponding theoretical framework, designing both offline and online scheduling algorithms, and illustrating their application in scheduling communication and computing tasks.

We start by the baseline scenario of batching task scheduling. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. We seek an optimal scheduling policy to maximize the overall system utility. We develop an algorithmic framework for the above scheduling problem in the generic form that can achieve 1/2-optimality, outperforming the best known result. We then demonstrate the application of our algorithmic framework to solve the generalized proportional broadcast problem by developing the first deterministic approximation algorithm.

We then formulate and analyze a fundamental downlink transmission scheduling problem in wireless communication systems, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously. In the problem, each request can be served by a subset of transmission strategies, and requests need to be served in the FIFO manner. We seek a downlink transmission scheduling algorithm maximizing the overall system utility. We first establish its hardness, and then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings, respectively.

The third contribution concerns the contiguous-resource batching task scheduling. A set of tasks need to be executed on a pool of continuous resource, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource; tasks are served in the FIFO manner. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. We establish the hardness of the problem and developing approximation scheduling algorithms for both offline and online settings.

Maison du doctorat de l'Université Paris-Saclay 2ème étage aile ouest, Ecole normale supérieure Paris-Saclay 4 avenue des Sciences, 91190 Gif sur Yvette, France

1 Figure 1 . 1 :

 111 Figure 1.1: Thesis organization

k

  denote the machine to which vertex v corresponds. Let Ĉ denote the set of colors in C b,tv,k not yet used by any neighbor of v. If there are at least N y * v colors in Ĉ, i.e., | Ĉ| ≥ N y * v , we color v using the first N y * v colors in Ĉ; otherwise, we color v using colors in Ĉ and the first N y * v -| Ĉ| colors in C not yet used by any neighbor of v.

•

  AvailableSameGroupColors(v, C * ) returns the set of colors in C * not yet used by any neighbor of v if such colors exist, and ∅ otherwise. • AvailableColors(v, n, C * ) returns the first n colors in C * not yet used by any neighbor of v.

5 : 12 :

 512 let b denote the group to which the task corresponding to v belongs 6: let k denote the machine to which vertex v corresponds 7: C b,tv,k ← SameGroupColors(b, t v , k, C) 8: Ĉ ← AvailableSameGroupColors(v, C b,tv,k ) color v using the colors in Ĉ and the colors AvailableColors(v, y * v N -| Ĉ|, C) 13:

  max v∈V w v • x v s.t. (3.2), (3.3),(3.5)

Figure 3 . 1 ,

 31 in which a subgraph of G 0 related to a single group b is shown.

Figure 3 . 1 :

 31 Figure 3.1: Illustration of a subgraph of G 0 related to group b: q *b,t h , 1 ≤ h ≤ 7, are 0.3, 0.3, 0.5, 0.5, 0.2, 0.9, 0.8

  and add the constructed edges to E 1 . Each constructed edge is a duplicate of the original edge and has the same endpoints. By the definition of z b t,k in the first step, we have 0 ≤ z b t,k ≤ 1 for any triple (t, k, b). Therefore, each original edge in G 0 is duplicated to at most N edges in G 1 .

  Based on the construction of G 0 , each slot in T b refers to at most two edges in E 0 corresponding to group b, and thus the number of edges in G 0 is O( i∈N λ i ) = O(λ). Thus, the construction of G 0 can be done in O(λ) time. As each edge u t v b k ∈ E 0 is duplicated by z b t,k N edges in E 1 , the number of edges in E 1 is O(λ • N ), and thus it follows from |C| = O( N ) that the complexity for coloring of the edges in E 1 is O(λ • N 2 ). Since the number of edges for each task i is upper-bounded by l i N , the number of edges in E 2 can be upper-bounded by O( i∈N l i N ). It then follows from N = λ 1+ that the complexity of Algorithm 2 is O(λ 3+2 ), asymptotically O(λ 3 ).

Figures 3 .

 3 Figures 3.2(a) and 3.2(b).We also analyze our algorithm performance using mean, variance confidence intervals (CI), which are listed in Table3.3 and 3.4.

Figure 3 . 2 :

 32 Figure 3.2: Performance gains of Algorithm 1

Figure 3 . 3 :

 33 Figure 3.3: Performance gains of Algorithm 2 for the proportional broadcast scheduling problem

j 2 .

 2 Therefore, Algorithm 1 uses at most N colors to color G 2 , and the number of colors already used to color the second class of neighbors is upper-bounded by N -y * v N . By combining the above analysis, when Algorithm 1 colors v, there are at most 2( N -y * v N ) colors already used to color the neighbors of v. As |C| = 2 N -1 and y * u N ≥ 1, there are at least y * u N available colors that can be used by Algorithm 1 to color v.

3. 8 . 4

 84 Proof of Lemma 3.3 Consider any vertex v ∈ V with ŷ * v N ≥ 1. Denote the task corresponding to v by i and the machine corresponding to v by k. The neighbors of v can be divided into the following two classes.

  Then, we can upper-bound the number colors already used to color the neighbors of v in G 1 by N -ŷ * v N . The second class of neighbors consist of the vertices that are connected with v by intra-task edges. It follows from the proof of Lemma 3.2 that the number of colors already used to color the second class of neighbors is upper-bounded by Nŷ * v N . By combining the above analysis, when Algorithm 1 colors v, there are at most 2( N -ŷ * v N ) colors already used to color the neighbors of v. As |C| = 2 N -1 and ŷ * v N ≥ 1, there are at least ŷ * v N available colors that can be used by Algorithm 1 to color v.

i.

  For each strategy r ∈ R and each packet b ∈ B, we denote τ r,b the time (in number of slots) to transmit packet b under strategy r. A more robust strategy can reach more users at the price of longer transmission time under a lower but more robust data rate.

Figure 4 . 1 :

 41 Figure 4.1: Illustration of our adapted FIFO model vs. standard FIFO model

Figure 4 .

 4 Figure 4.1 illustrate the possible executions of the requests, with the length being the requested execution time.

Definition 4 . 2 (

 42 Feasible Scheduling Policy for Downlink Transmission Scheduling).

Theorem 4 . 1 (

 41 Hardness of P3). The offline scheduling problem P3 is NP-hard. Its discrete version is NP-complete.

Example 4 . 2 .

 42

Figure 4 . 16 vFigure 4 . 2 :

 41642 Figure 4.2: Illustration of vertex construction for Example 4.2

  whose priorities are assigned the priority level i. It then holds that the total number of vertices sums up to O(δRM ). Listing users in N b , ∀1 ≤ b ≤ B takes O(N ) time. Consider each packet b and each corresponding active slot t. Among the users in N b , listing the set of users in N b,t takes O(|N b |) time. For each strategy r, among the users in N b,t , listing the set of active users at t under r takes O(|N b,t |) time.

Lemma 4 . 1 .

 41 Each IS of G maps to a feasible policy. Each optimum feasible policy maps to an IS of G.

Lemma 4 .

 4 1 immediately leads to the following corollary.

Corollary 4 . 1 .

 41 P3 can be cast to the MWIS problem, formulated below. maximize v∈V w v y v subject to y v + y u ≤ 1, ∀uv ∈ E (4.1)

vN ≥ 1

 1 is colored by y * v N colors in Lemma 4.2, based on which we are then able to establish the approximation factor of Algorithm 3 in Theorem 4.2. We conclude this subsection by giving the complexity of Algorithm 3.

Lemma 4 . 2 .Theorem 4 . 2 .

 4242 Each vertex v ∈ V with y * v N ≥ 1 is colored by y * v N colors by Algorithm 3.Proof Sketch. We first derive the upper bound of the number of colors that have been used to the neighbors of v when Algorithm 3 colors v. Based on the number of colors disposed in C, we can then derive that there are at least y * v N available colors that can be used to color v. Algorithm 3 outputs an asymptotically 1/(1 + ϕ/l min )-optimal feasible scheduling policy for our offline scheduling problem, i.e., Algorithm 3 is a 1/(1 + ϕ/l min )-approximation algorithm.Proof Sketch. It follows from Lemma 4.1 and Lemma 4.2 that we get at most(1 +

  i.e., r b = argmin r∈R i ,i∈Ωt∩N b τ r,b . We then seek the packet b such that the total reward of the users in Ω t ∩ N b under strategy r b is maximum among the packets in B(Ω t ). Let Γ denote the set of users in Ω t requesting packet b. Finally, we start serving the users in Γ at slot t by transmitting packet b under the strategy r and the priority of request min k∈Γ k.

  ,b i , and there are 5 strategies indexed from 1 to 5, i.e., R = 5. We run three experiments with B = 5, 10 and 20 respectively. The simulation results of the offline and online cases are illustrated in Figures 4.3and 4.4.

Figure 4 . 3 :

 43 Figure 4.3: Performance gains of Algorithm 3 for the first scenario in offline case

Figure 4 . 4 :

 44 Figure 4.4: Performance gains of Algorithm 4 for the first scenario in online case

  ∀i ∈ N . The simulation results for this scenario are shown in Figures 4.5 and 4.6. From the results, we derive the following observations.

Figure 4 . 5 :

 45 Figure 4.5: Performance gains of Algorithm 3 for Scenario 2 in offline case

Figure 4 . 6 :

 46 Figure 4.6: Performance gains of Algorithm 4 for Scenario 2 in online case

Figure 4 . 7 :Figure 4 . 8 :

 4748 Figure 4.7: Performance gains of Algorithm 3 for Scenario 3 in offline case

0- 1

 1 Knapsack problem. Given a positive capacity C and a set N of N elements indexed from 1 to N , each with a positive weight c i (i ∈ {1, 2, • • • , N }), find a set S ⊆ {1, 2, • • • , N } such that i∈S c i ≤ C and i∈S c i is maximized. The problem is

  of v is upper-bounded by (1+ϕ/l min ) N -2 y * v N . As |C| = (1+ϕ/l min ) N -1 and y * v N ≥ 1, there are at least y * v N available colors in C when Algorithm 3 colors v. Thus, v is colored by y * v N colors. The lemma is thus proved.

4. 7 . 5

 75 Proof of Theorem 4.2 Denote the utility of the optimal solution of P3 by OP T . Clearly, the set of vertices sharing a same color is an IS of G. It follows from Lemma 4.1 that each IS of G maps to a feasible scheduling policy. It follows from Lemma 4.2 and |C| ≤ (1+ϕ/l min ) N -1 that Algorithm 3 outputs a coloring of G using at most (1+ϕ/l min ) N -1 colors. We thus get at most (1 + ϕ/l min ) N -1 ISes, denoted by I i , 1 ≤ i ≤ I, where I ≤ (1 + ϕ/l min ) N -1.

Figure 5 . 1 :

 51 Figure 5.1: Illustration of an admitted request i

Figure 5 . 3 : 2 Example 5 . 2 .

 53252 Figure 5.3: Illustration of vertex construction for Example 5.2

Figure 5 . 12 vFigure 5 . 4 :

 51254 Figure 5.4: Illustration of type-1 and type-2 edges in G

  is at most one type-2 constraint. The complexity for listing all vertices in V c (i) is upper-bounded by k∈N ,k≤i δ k (F -f k + 1). Hence, listing type-2 constraints takesO(N k∈N ,k≤i δ k (F -f k + 1)) = O(N i∈N δ k (F -f k + 1)), asymptotically O(δN F ), time.By combining the above analysis, we can replace the constraints (5.1) and (5.2) by constraints (5.3), (5.4), (5.5) to transform the LP relaxation of the RIS problem to the LP problem below, denoted by P4'. P4': maximize v∈V w v y v subject to (5.3), (5.4),(5.5)

  Figures 5.5 and 5.6.

Figure 5 . 5 :

 55 Figure 5.5: Performance gains of Algorithm 5 for Scenario 1 in offline case

Figure 5 . 6 :

 56 Figure 5.6: Performance gains of Algorithm 6 for Scenario 1 in online case

Figure 5 . 9 :Figure 5 . 10 :

 59510 Figure 5.9: Performance gains of Algorithm 5 for Scenario 3 in offline case

5. 7 . 9

 79 Proof of Theorem 5.2 Denote the utility of the optimal feasible scheduling policy by OP T . Let A (D 1 + f max • D 2 ). We have shown that each color induces a RIS of G in Lemma 5.5. It follows from Lemma 5.4 that the coloring of V uses at most A N -f max colors. We thus get at most A N -f max RISes, denoted by Vi , 1 ≤ i ≤ I, where I ≤ A N . Let I * denote the RIS output by Algorithm 5. Since each vertex v in G is replaced by y * v N new vertices, each of which is colored by Algorithm 5, we have v∈I * inequality follows that the value of an optimal fractional LP solution is an upper bound on the value of the feasible scheduling policy and the total value decreased by Step 1 is upper-bounded byv∈V f min + 1)δ 1+ i∈N v∈V + i (w v + k∈N + v r∈V k ,v≺r w r ) ≤ (F -f min + 1)δ (F -f min + 1)δ 1+ max i∈N max j∈N + v r∈V j ,v≺r w r ),where the equal follows from that each induced vertex has only one parent, and the first inequality follows from that there are at most (F -f min + 1)δ elementary vertices in V.As it holds that max i∈N max v∈V + i (w v + j∈N + v r∈V j ,v≺r w r ) ≤ OP T,

Titre:

  Planification des tâches de calcul et de communication par lots: base théorique et conception d'algorithmes Mots clés: Algorithmes d'approximation, Traitement par lots, Ordonnancement Résumé: Dans cette thèse, nous formulons et analysons une classe de problèmes fondamentaux d'ordonnancement des tâches découlant d'une variété de systèmes informatiques et de communication émergents : les tâches sont divisées en groupes; celles d'un groupe peuvent être mises en lots et exécutées simultanément; l'objectif de l'ordonnanceur est de concevoir des algorithmes d'ordonnancement maximisant l'utilité globale du système. Sous le parapluie générique ci-dessus, nous étudions différentes classes de problèmes d'ordonnancement de tâches par lots, en établissant le cadre théorique correspondant, en concevant des algorithmes d'ordonnancement hors ligne et en ligne, et en illustrant leur application dans la planification des tâches de communication et d'informatique. Nous commençons par le scénario de base de l'ordonnancement des tâches par lots. Il y a un ensemble de tâches à exécuter sur un certain nombre de machines. Certaines tâches peuvent être exécutées simultanément sur une seule machine, tandis que d'autres nécessitent l'utilisation exclusive d'une machine entière. Nous recherchons une politique d'ordonnancement optimale pour maximiser l'utilité globale du système. Nous développons un cadre algorithmique pour le problème d'ordonnancement ci-dessus dans la forme générique qui peut atteindre 1/2-optimality, surperformant le résultat le plus connu. Nous démontrons ensuite l'application de notre cadre algorithmique pour résoudre le problème de diffusion proportionnelle généralisée en développant le premier algorithme d'approximation déterministe. Nous formulons et analysons ensuite un problème fondamental de programmation de transmission en liaison descendante dans les systèmes de communication sans fil, composé d'une station de base et d'un ensemble d'utilisateurs, chacun demandant un paquet à servir dans une fenêtre de temps. Certains paquets sont demandés par plusieurs utilisateurs et peuvent être servis simultanément. Dans le problème, chaque demande peut être servie par un sous-ensemble de stratégies de transmission, et les demandes doivent être servies de la manière FIFO. Nous recherchons un algorithme de programmation de transmission en liaison descendante maximisant l'utilité globale du système. Nous établissons d'abord sa dureté, puis développons des algorithmes d'approximation avec une garantie de performance mathématiquement prouvée en termes d'approximation et de rapports compétitifs pour les paramètres hors ligne et en ligne, respectivement. La troisième contribution concerne l'ordonnancement des tâches de mise en lots des ressources contiguës. Un ensemble de tâches doit être exécuté sur un pool de ressources continues, chacune nécessitant un certain temps et une ressource contiguë; certaines tâches peuvent être exécutées simultanément en lot en partageant la ressource, tandis que d'autres nécessitent une utilisation exclusive de la ressource; les tâches sont servies de la manière FIFO. Nous recherchons une allocation optimale des ressources et la politique d'ordonnancement connexe maximisant l'utilité globale du système. Nous établissons la dureté du problème et développons des algorithmes de programmation d'approximation pour les paramètres hors ligne et en ligne. Maison du doctorat de l'Université Paris-Saclay 2ème étage aile ouest, Ecole normale supérieure Paris-Saclay 4 avenue des Sciences, 91190 Gif sur Yvette, France Title: Scheduling Batching Computing and Communication Tasks: Theoretical Foundation and Algorithm Design Keywords: Approximation Algorithm, Batching, Task Scheduling

Table 3 .

 3

	1: Main notations

i set of machines on which task i can be executed l i,k number of slots task i needs to be executed on machine k w i,k reward of task i if it it executed on machine k x i,k binary variable indicating whether task i is executed on machine k t i,k time to start executing task i on machine k

Table 3 .

 3 3: Mean, variance and confidence intervals in bounded case

	N	50	100	150	200	250
	Mean	0.9843	0.9356	0.8828	0.8940	0.8771
	Variance	0.0144	0.0155	0.0230	0.0212	0.0315
	CI (95%) [0.9788,0.9897] [0.9297,0.9415] [0.8740,0.8915] [0.8860,0.9021] [0.8652,0.8891]
	N	300	350	400	450	500
	Mean	0.8678	0.8487	0.8535	0.8544	0.9058
	Variance	0.0424	0.0292	0.0429	0.0484	0.0449
	CI (95%) [0.8517,0.8839] [0.8376,0.8598] [0.8373,0.8698] [0.8360,0.8728] [0.8887,0.9229]

Table 3 .

 3 4: Mean, variance and confidence intervals in unbounded case

	N	50	100	150	200	250
	Mean	0.9881	0.9295	0.8913	0.8933	0.8747
	Variance	0.0149	0.0210	0.0289	0.0276	0.0297
	CI (95%) [0.9824,0.9937] [0.9215,0.9374] [0.8802,0.90224] [0.8828,0.9038] [0.8634,0.8860]
	N	300	350	400	450	500
	Mean	0.8642	0.8625	0.8430	0.8639	0.9078
	Variance	0.0375	0.0434	0.0326	0.0549	0.0351
	CI (95%) [0.8499,0.8784] [0.8460,0.8789] [0.8306,0.8553] [0.8431,0.8847] [0.8944,0.9211]

Table 3 .

 3 5: Mean, variance and confidence intervals for proportional broadcast scheduling

	N	50	100	150	200	250
	Mean	0.9718	0.9678	0.9729	0.9685	0.9762
	Variance	0.0140	0.0211	0.0166	0.0154	0.0142
	CI (95%) [0.9677,0.9758] [0.9617,0.9738] [0.9682,0.9776] [0.9641,0.9729] [0.9721,0.9803]
	N	300	350	400	450	500
	Mean	0.9839	0.9871	0.9889	0.9917	0.9913
	Variance	0.0115	0.0109	0.0108	0.0077	0.0092
	CI (95%) [0.9806,0.9871] [0.9840,0.9902] [0.9857,0.9919] [0.9894,0.9938] [0.9887,0.9939]

  1 . Each request i (1 ≤ i ≤ N ) is characterized by a couple (a i , d i ), where a i denotes the arrival time of the request at the base station, d i denotes its deadline, i.e., request i needs to be finished by time d i if it is served, d i -a i + 1 denotes the slackness of i. Let b i denote the packet requested by user i. A packet may be requested by multiple users, creating potential data sharing opportunities due to the broadcast nature of the wireless medium. Throughout our analysis, we use the terms user and request interchangeably.There are B packets, indexed from 1 to B, in the base station. We normalize the slot duration to 1 for notation conciseness and regard all the time instances such as a i and d i as integers, otherwise we can perform a straightforward rounding process. Table4.1 lists the main notations in this chapter.

		Table 4.1: Main notations
	N	user set
	N	number of users in N , N = |N |
	T	time horizon in number of time slots
	R	set of transmission strategies in the base station
	R	number of strategies in R, i.e., R = |R|
	B	total number of packets
	a i	arrival time of user i
	d i	deadline of user i
	b i	packet requested by user i
	w i,r	reward of request i under strategy r
	R i	set of transmission strategies covering request i
	r *

i least robust strategy in R i τ r,b number of slots to transmit packet b under strategy r N b set of users requesting packet b N b,t set of users in N b active at slot t N + b,t (i, r) set of active users in N b at slot t under r whose index ≥ i N - b,t (i, r) set of active users in N b at slot t under r whose index ≤

Table 4 .

 4

		2: Constructed vertices in Example 4.2
	Vertex Covered user(s) Priority Time interval Strategy
	v 1	1,3	1	[0,1)

Table 4

 4

	.3 lists the additional notations used in

Table 4 .

 4

3: Additional notations in Sections 4.3.4 to 4.3.6

  Let l min min 1≤b≤B min r∈R τ r,b and l max max 1≤b≤B max r∈R τ r,b . For each slot t ∈ [0, l min -2], the vertices active at slot t are also active at l min -1. Similarly, for each slot t ∈ [T -l min +2, T ], each vertex active at slot t is also active at slot T -l min +1. Therefore, we just need to list type-1 constraints for slots t ∈ [l min -1, T -l min + 1], and each slot corresponds to at most one type-1 constraint. Hence, there are at most T -2l min + 1, asymptotically O(T ), type-1 constraints.

	Type-1 constraints:	y v ≤ 1, ∀t ∈ [0, T ].	(4.2)
	v∈V,v is active at slot t
	Type-2 constraints. The second type of constraints, as shown in (4.3), concerns

The first type of constraints, as shown in (4.2), concerns the vertices in V and type-1 edges. For each time slot t ∈ [0, T ], we call a vertex v active at

slot t if t ∈ [t v , t v + l v -1]

. The intuition behind the definition of active vertex is that if the corresponding requests are instantiated by an active vertex at slot t, then the requests are still in serving at slot t. Recall the construction of the request graph G, the vertices in V that are active at slot t are adjacent to each other. Type-1 constraints state that at most one active vertex at slot t is chosen at any feasible scheduling policy. the vertices in V and type-2 edges. For each time slot t, we call a vertex v valid at slot t if t v ≥ t. Any request instantiated by a valid vertex v at t does not start being served earlier than t. For any user i, let V α (i) denote the set of vertices v ∈ V satisfying:

[START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF]

Table 4 .

 4 .4 lists the additional notations used in Section 4.4. 4: Additional notations in Section 4.4

	T	set of slots at which Algorithm 4 starts serving at least one request
	O	set of requests that are served by the optimal scheduling policy
	Ω t	set of ready requests at slot t
	B(Ω t ) set of packets, each requested by at least one user in Ω t
	B max max 1≤t≤T |B(Ω t )|
	N * t	set of requests that start being served by Algorithm 4 at slot t

  i is the time to start serving user i if its request is admitted, x i,r is the decision variable indicating whether to serve user i under strategy r, r i and β i are the transmission strategy and priority under which user i is served, respectively. Constraint (4.4a) implies that if any pair of requests is served under different strategies, the time intervals to serve them cannot overlap. Constraint (4.4b) implies that if any pair of served users requests different packets, the time intervals to serve them cannot overlap. Constraints (4.4c) and (4.4d) correspond to the adapted FIFO model. Constraint(4.4c) indicates that for any pair of request i and j, if request j is served under the lower priority than the priority under which request i is served, the time to start serving j cannot be earlier than the time to start serving i. Constraint (4.4d) implies that if request j is served, it must be served under the priority of itself or batched with a request with highest priority among the served users who request the same packet as j and whose time intervals can fit for serving j. Constraint (4.4e) indicates that if user i is served, i should be served under a strategy in R i and there is enough time to transmit the requested packet to user i by its deadline.

.4e)

x i,r i ∈ {0, 1}, ∀i ∈ N , ∀r ∈ R i

where t

Table 5 .

 5

	1: Main notations

Table 5

 5

	.3 lists the additional notations used in

Table 5 .

 5 3: Additional notations in Sections 5.3.4, 5.3.5, and 5.3.6V α (t, s) set of active elementary vertices in V at (t, s) B α (t, s) set of active groups at (t, s) V c (i) set of elementary vertices valid at slot max{0, a i + l b -L b } corresponding to the request j with j ≤ i for a request i B c (i) set of groups, each of which has at least one vertex in V c (i) N c (i) set of requests, each of which has at least one vertex in V c (i)

	y * v	value of y v in the LP relaxation of the RIS problem
	λ	max k∈N (d k -a k + 1)
	l min	min k∈N l k
	l max	max k∈N l k
	D 1

Table 5 .

 5 served requests such that i can reuse the time-frequency block of the requests if there is at least one such request, (2) if there is no request that is being served at slot t, we start serving the requests at slot t belonging to one group after another according to the total reward of the requests for each group under the constraint of the amount of available frequency band.Technically, we introduce the following definitions. We say a slot occupied if there exists a request being served at the slot. For each slot t, we say a request k ready at slot t satisfying: (1) a k ≤ t ≤ d k -l k + 1, (2) k has not been served before slot t, and(3) starting serving k at slot t does not violate the adapted FIFO model. For each slot t, let Ω t denote the set of ready requests at slot t. Let B(Ω t ) denote the set of groups, each of which has at least one request in Ω t . Let N - t denote the set of requests that start being served earlier than slot t. We use a quadruple (i, t i , s i , β i ) to denote each served request i, where t i and s i are the starting time and the starting spectrum to serve request i, and β i is the priority to serve i.

		4: Additional notations in Section 5.4
	s i	frequency to start serving i
	t i	starting time to serve request i
	Ω t	set of active requests at the current slot
	B(Ω t )	set of groups containing at least a request in Ω t
	B max	max 0≤t≤T |B(Ω t )|
	N * t N -t	set of requests started being served at slot t by Algorithm 6 set of requests started being served earlier than slot t
	T	set of slots, at which Algorithm 6 starts serving at least one
		request under the priority of itself
	In the online setting, we focus on the non-preemptive scheduling model: once a
	request starts being served, it must be completed without interruption [19] [21]. We
	note that the non-preemptive model is seamlessly compatible with our adapted FIFO

model. Our analysis can be extended to the other models such as the preemptive-resume and the preemptive-restart models. the

Table 5 .

 5 5: Additional notations in the Appendix Knapsack problem. Given a positive capacity C and a set N of N elements indexed from 1 to N , each with a positive weight w i and size c i

	x i	decision variable indicating whether to serve user i
	V α b,τ (t, s)	set of elementary vertices in V α (t, s) of group b whose left
		boundaries are slot τ
	N α b,τ (t, s)	set of requests having at least one vertex in V α b,τ (t, s)
	V c τ (i)	set of elementary vertices in v ∈ V c (i) with t v = τ
	N c τ (i)	set of requests having at least one vertex in V c τ (i)
	O	set of requests served by the optimal scheduling policy
	5.7.2 Proof of Theorem 5.1
	To prove its hardness, we consider the classical 0-1 Knapsack problem which is
	known to be NP-hard [26].
	0-1

  ∈T i∈Ωt w i , i.e., i∈O w i ≤ τ ∈T i∈Ωt w i . Consider each slot t ∈ T . Because each request i satisfies f i ≤ F , in the first iteration of slot t Algorithm 6 starts serving all requests in Ω t of group b * at slot t, i.e., {k : k ∈ Ω t , b k = b * } ∈ N * t , where b * = argmax b∈B(Ωt) k∈Ωt,b k =b w k , the total reward of requests in Ω t is Therefore, the total reward of the optimum scheduling policy can be upper-bounded It follows from the definitions of T and N * t that the utility of Algorithm 6 is at least t∈T i∈N * t w i . Hence, Algorithm 6 has B max competitive ratio if the slackness for each request i is at least l max + l i -1.

	Chapter 6
	Conclusion and Prospective
	w i ≤ τ i∈Ωt b∈B(Ωt) k∈Ωt,b k =b w k 6.1 Thesis Summary
			≤ |B(Ω t )| •	w k
				k∈Ωt,b k =b *
			≤ |B(Ω t )| •	w i .
				i∈N * t
	by
	w i ≤	w i ≤	|B(Ω t )|	w i ≤ B max •	w i .
	i∈O	t∈T i∈Ωt	t∈T	i∈N * t	t∈T i∈N * t
			121

Strictly speaking, the problem corresponds more to the multicast setting from a networking perspective. In this thesis, we stick to the term broadcast to be coherent to the related literature on this problem.

An independent set of a graph is a set of vertices, no two of which are linked by an edge. The maximum weighted independent set is to find the independent set maximizing the sum of weights of the vertices in the independent set.

Our analysis extends straightforwardly to the case where a user can request more than one packets by creating duplicates of the user and regarding each duplicated user as a new one.

Acknowledgements

We further conduct numerical analysis to evaluate the performance of our approximation algorithms.

Proof. We consider the following instance of our online scheduling problem. There is only one packet and one strategy in the base station; the station needs 2 slots to transmit the packet under the strategy. In slot 0, a request with the couple (0, 1) arrives, and its reward is 1 if it is served under the strategy. We distinguish two cases.

• If Π does not serve the request, then no more request arrives, leading to a competitive ratio of infinity as the optimal solution is clearly to serve the request;

• If Π serves the request, a set of requests arrive, each characterized by the same couple [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF][START_REF] Agrawal | Optimality of certain channel aware scheduling policies[END_REF], and the total reward of them is larger than ρ if they are served under the strategy. Under this request sequence, the optimal scheduling policy serves the requests arriving at slot 1, while Π only serves the request arriving at slot 0, leading to a competitive ratio of larger than ρ.

Combining the above two cases completes our proof.

Online Scheduling Algorithm Design

Theorem 4.3 establishes the inapproximability of the online downlink scheduling problem in the generic case. By examining the problem instance in Theorem 4.3, we observe that the inapproximability is significantly due to the stringent deadline.

Consequently, an online algorithm is forced to make a decision immediately when the requests arrive. Motivated by this observation, we slightly relax the slackness of the requests, and design an online scheduling algorithm with bounded competitive ratio. Specifically, we assume that the slackness of each request i is at least l max +min r∈R i τ r,b i -1, i.e., d i -a i + 1 ≥ l max + min r∈R i τ r,b i -1, ∀i ∈ N . Moreover, for each user i and each pair of strategies r, r ∈ R i with r ≺ r , we assume that w i,r ≥ w i,r .

We give a high-level overview of our online scheduling algorithm. For each slot t, at which there is no request being served, our algorithm starts serving a set of users at slot t requesting a same packet under the least robust strategy covering the users such that the total reward of the users is maximum among the packets.

Technically, we introduce the following definitions. We say a slot free if there is no request being served at the slot. For each slot t, we say a request k ready at slot t satisfying: [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF] k is active at slot t, i.e., a k ≤ t ≤ d i -min r∈R i τ r,b i + 1, (2) k has not been served before slot t, and (3) starting serving k at slot t does not violate the adapted FIFO model. Let Ω t denote the set of ready requests at slot t, and let B(Ω t ) denote the packets, each of which is requested by at least one user in Ω t . We define if TotalReward(Γ * , r * )>TotalReward(Γ, r) then If the slackness of each request is at least l max + min r∈R i τ r,b i -1, i.e., d i -a i + 1 ≥ l max + min r∈R i τ r,b i -1, ∀i ∈ N , the competitive ratio of Algorithm 4 is upper-bounded by B max , i.e., Algorithm 4 outputs a 1/B max -optimal feasible scheduling policy.

Proof. Let T denote the set of slots, at each of which Algorithm 4 starts serving at least one request. We first prove that the utility of the optimal scheduling policy is upper-bounded by the total reward of the requests, each of which is ready at a slot in T . For each slot t ∈ T , we then derive the relationship between the total reward of the requests starting being served by Algorithm 4 at slot t and the total reward of the ready requests at slot t. Combining the above results allows us to establish B max -competitive of Algorithm 4. Theorem 4.4 shows that the performance of our algorithm only scales with the largest B(Ω t ), which only depends on the number of packets that are requested by the ready users at the current slot t. Therefore, the global efficiency of our algorithm does not degrade with the system size.

Numerical Analysis

In this section, we conduct numerical analysis to evaluate the performance of the constant-factor offline and online scheduling approximation algorithms we develop. In our simulation, we trace the metric (3.8) to evaluate the performance of the optimum By combining the above analysis, the set of vertices in V * is an IS of G and covers all requests in N * , where the proof of the second property is completed.

Proof of Lemma 4.2

It follows from Algorithm 3 that the colors that cannot be used to v have been used to the neighbors of v when Algorithm 3 colors v. We first prove that the number of colors that have been used to the neighbors of v is upper-bounded by (1 + ϕ/l min ) N -2 y * v N when Algorithm 3 colors v. The neighbors of v can be divided into the following three classes.

The first class of neighbors consist of the vertices that are connected with v by type 1 edges. When coloring the vertex v, all vertices u with t u < t v have been colored and no vertex u with t u > t v is colored because we color the vertices in V in non-decreasing order by their starting time. Thus, the colors, which cannot be used to v, have been used to color the first class of neighbors of v that are active at slot t v . It follows from the constraint (4.2) that u∈V,u is active at slot tv

Therefore, the number of colors that have been used to color the first class of neighbors of v is upper-bounded by N -y * v N when Algorithm 3 colors v.

The second class of neighbors consist of the vertices that are connected with v by type-2 edges. For each user k ∈ N , it follows from the constraints (4.3)

where the last inequality follows from max

Therefore, the colors that are used to the vertices in V α (k) is upperbounded by ϕ l min • N . For each request k, we assume that the vertices in V α (k) are adjacent to each other in the current proof. Clearly, the edges connecting each pair of vertices in V α (k) include all type-2 edges between the vertices in V α (k).

Based on the construction of type-2 edges, there is no type-2 edge between any vertex in V α (k 1 ) \ V α (k 2 ) and any vertex in V α (k 2 ) \ V α (k 1 ). When Algorithm 3 colors Chapter 5

Contiguous-resource Batching Task

Scheduling

This chapter investigates a two-dimensional task scheduling problem, where a set of tasks need to be executed on a pool of continuous resource, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource; tasks are served in the FIFO manner. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. The above problem is termed as contiguous-resource batching task scheduling problem. The scheduling problems addressed in the previous two chapters can be regarded as the degenerated instances of the contiguous-resource batching task scheduling problem, where tasks require the entire resource in one of the dimension.

Compared with existing works on bandwidth and storage allocation problem in Section 2.4, and task scheduling problem in Section 2.2, our contiguous-resource batching task scheduling problem we address has the following constraints that has not been holistically addressed before: (1) the allocated resource for each request must be contiguous, (2) the requests are divided into non-overlapping groups, with those in the same group executable in batched, (3) the requests should be served by the adapted FIFO model. We note that it is the combination of these constraints that makes our problem non-trivial and requires a systematical treatment.

In this chapter, we investigate both offline and online scheduling settings. In both cases, we first establish the problem hardness and then develop approximation algorithms with proven performance guarantee. We further complement our theoretical analysis with numerical simulations that demonstrate the effectiveness of our algorithms

In our problem, the standard FIFO model needs to be adapted as below to take into account spectrum reuse. Definition 5.1 (Adapted FIFO model). Any scheduling policy satisfying the following requirement is called an adapted FIFO model. When serving request i, any request j > i that can reuse the spectrum of i must also be served simultaneously with request i, as long as j can fit in the service time of i and the spectrum allocated to i. We remark that (1) the adapted FIFO model takes into account the spectrum reuse and is thus more flexible and naturally leads to better efficiency, as demonstrated by the illustration example, (2) it is technically more involved than the standard FIFO model.

In the adapted FIFO model, for a number of requests served simultaneously, among which the highest priority request is i, we say that these requests are served, or batched, under the priority i by reusing the spectrum allocated to i, and we call i the head of the batched requests.

We conclude this section by defining the feasible scheduling policy for contiguousresource batching task scheduling.

Definition 5.2 (Feasible Scheduling Policy for Contiguous-resource Batching Task Scheduling). We call a scheduling policy feasible if

• it is an adapted FIFO model;

• each request is served at most once;

• the time-frequency blocks allocated to any pair of requests from different groups do not overlap.

The Offline Case

Problem Formulation and Hardness

In this section, we consider the offline channel bonding problem, denoted by P4. In the following theorem, we prove that P4 is NP-hard. To make our presentation more streamlined, we provide integer linear programming formulation of P4 and the proof sketch of the lemmas and theorems in the main text and defer the detailed proof in Appendix 5.7.

Theorem 5.1 (Hardness of P4). P4 is NP-hard. Its discrete version is NP-complete.

Proof Sketch. We prove that the classical 0-1 Knapsack problem can be reduced to P4.

It then follows from the NP-hardness of the 0-1 Knapsack problem that P4 is NP-hard.

It follows from NP-completeness of Knapsack problem with integer weights that the discrete version of P4 is also NP-complete.

Given the NP-hardness of P4, we devote our efforts to designing approximation algorithms. Our central idea is to construct a graph, termed as request graph, to capture the relationships among requests, given spectrum reusability and the constraint imposed by the adapted FIFO model. We then cast P4 to the MWIS problem in the constructed request graph.

Conceptually, we can instantiate P4 on an Euclidean plan with the x-axis being time and the y-axis being frequency. Each request i can then be cast to an axis-aligned rectangle of height f i , length l i whose reward is w i . In order to be served, the above rectangular needs to be located within the rectangle

to the problem of finding a subset of rectangles corresponding to different requests maximizing the total reward, by taking into account the adapted FIFO model and spectrum reusability.

The main part of this section is organized in five subsections. We first construct the request graph and cast P4 to the problem of MWIS. We then explore the structural properties of the constructed request graph to formulate the LP relaxation of P4.

We further develop an approximation algorithm based on rounding the solution of the LP relaxation to an integer solution. The approximation ratio of our algorithm is established to complete the section.

Request Graph

The request graph, denoted by G (V, E), consists of the following vertices and edges.

Vertices

We construct the following two types of vertices.

Elementary vertices. For each request i ∈ N , we create a vertex for each rectangle of height f i and length

We call these vertices the elementary vertices of i. Let t v and s v denote the left boundary (i.e., the starting time) and the lower boundary (i.e., the starting spectrum) of the rectangle corresponding to v. Let l v and h v denote the length and height of the rectangle corresponding to v.

Each elementary vertex v of i corresponds to the execution of

If the scheduler decides to execute i using the time-frequency block corresponding to v, we say that i is instantiated by v. To take into account the adapted FIFO model, each elementary vertex of request i of 1 in slot 0, requests 2 and 5 under the priority of 2 in slot 1, request 4 under the priority of 4 in slot 3, maps to vertices v 1 , v 4 , v 3 , v 13 , and v 12 .

We now analyze the complexity of creating the vertices in G. Denote R max 1≤b≤B (F b -

). There are (F -f i + 1)(d i -a i -l i + 2) elementary vertices for each request i. The total number of elementary vertices sums up to O((F -f min )δ). For each elementary vertex v, there are j∈N + v (l v -l j + 1)(h v -f j + 1) induced vertices reusing the time-frequency block of v, and the complexity for listing the requests in

Hence, the total number of vertices sums to O(RM (F -f min )δ), and the construction of the vertices in

Edges

We construct the following three types of edges.

Type-1: inter-user edges characterizing interference among requests belonging to different groups. For each pair of elementary vertices v ∈ V + i and u ∈ V + j with b i = b j , we construct an edge between v and u if their corresponding rectangles overlap, making it impossible to instantiate i by v and also j by u.

Type-2: inter-user edges modeling adapted FIFO model. This type is further classified into two cases.

From Channel Bonding to Maximum Weighted Regular Independent Set

Armed with the constructed request graph G, we can cast P4 to the MWIS problem, more precisely, a variant of the MWIS problem called maximum weighted regular independent set problem. We start by defining the regularly independent set (RIS), which can be regarded as an enhanced version of IS adapted to our problem with frequency reuse. By choosing an IS in G we mean to serve the requests instantiated by the vertices in the chosen IS.

Definition 5.3 (Regular Independent Set). Given the request graph G, a vertex set V ⊆ V is a regular independent set if it satisfies the following two properties.

• Any pair of vertices in V is not adjacent to each other.

• The parent of any induced vertex in V is also in V.

The first property corresponds to the standard IS definition. The second captures spectrum reuse. In the following lemma, we show that each feasible scheduling policy maps to a RIS in G.

Lemma 5.1. Each feasible scheduling policy maps to a RIS of G.

Proof Sketch. Consider any feasible policy mapping to a subset of vertices in V. We first derive a contradiction if the subset of vertices contains two neighboring vertices, indicating that each feasible policy maps to an IS. Based on the definitions of the feasible scheduling policy and the adapted FIFO model, we then prove that the parent of any induced vertex in the subset is also in the subset.

Therefore, if we can find a MWRIS and turn it into an optimal feasible scheduling policy, the obtained scheduling policy is an optimal solution of P4. We thus concentrate on the MWRIS problem formulated as below.

3). We can check that (5.3) holds at any feasible scheduling policy.

u∈V j ,v≺u

It is well-known that the LP relaxation of the MWIS problem suffers the so-called half integer effect due to the edge constraint [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF]. To mitigate this effect, we add the specific constraints of our scheduling problem to the LP relaxation. In this regard, the pivotal technical challenge is to construct appropriate constraints such that [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF] any feasible scheduling policy is still feasible in the relaxed problem, (2) non-feasible solutions are eliminated as many as possible to facilitate the rounding process and to ensure the quality of the rounded integer solution. Given this challenge, we use the following two types of constraints to replace the edge constraint (5.1), where each type concerns a type of edges constructed in G, and thus corresponds to the specific constraint of our problem.

Type-1 constraints. The first type of constraints, as shown in (5.4), captures the interference among requests. For each resource block (t, s)

Type-1 constraints:

Lemma 5.2 proves that any feasible scheduling policy satisfies type-1 constraints.

Hence, imposing them does not lose any feasible scheduling policy.

Lemma 5.2. Any feasible scheduling policy satisfies type-1 constraints.

Proof Sketch. Consider each group b and each (t, s) pair. We first prove that the number of elementary vertices in V α (t, s) of group b at any feasible scheduling policy is upperbounded by

We then prove that the vertices in V α (t, s) at any feasible scheduling policy belong to a same group. Therefore, for each (t, s) pair, the size of V α (t, s) at any feasible scheduling policy is upper-bounded by

Let l min min k∈N l k and l max max k∈N l k . We next derive the number of type-1 constraints. For each (t , s ) pair, where t ∈ [0,

and s ∈ [0, F ], the vertices active at (t , s ) are also active at (l min -1, s ). Therefore, we just need to list type-1 constraints for the pairs (t, s)

As each pair corresponds to at most one type-1 constraint, there are in total O((F -2f min )(T -2l min )), asymptotically O(F T ), type-1 constraints.

Type-2 constraints. The second type of constraints, as shown in (5.5), captures the adapted FIFO model. For each time slot t, we call a vertex v valid at slot t if t v ≥ t.

For any request i of group b, let V c (i) denote the set of elementary vertices that are valid at slot max{0, a i + l min -l max } and that correspond to requests j ∈ N with j ≤ i, i.e., request i and requests in N with higher priority than i. For each elementary vertex u of request k, based on the construction of G, the vertices, which are connected with u by type 2 edges, are valid at slot max{0, a k + l k -l v }. It follows from l k ≥ l min , l v ≤ l max that a k + l k -l v ≥ a k + l min -l max . Therefore, V c (i) includes all elementary vertices v satisfying: (1) v is connected with one of the vertices in V i by a type 2 edge, and

(2) β v ≤ i. Let B c (i) denote the set of groups, each of which has at least one vertex in V c (i). Let N c (i) denote the set of requests, each of which has at least one vertex in

For each group b ∈ B c (i), Lemma 5.3 proves that the number of vertices in V c (i) belonging to group b is upper-bounded by (l max -l min + 1) 2 (f max -f min + 1) at any feasible scheduling policy.

Lemma 5.3. For each group b ∈ B c (i), there are at most (l max -l min + 1) 2 (f max - for each request k ∈ N + v do 10:

end for 12: end for 13: sort the elementary vertices v in V lexicographically based on (t v , s v ) with ties broken randomly 14: for each elementary vertex u ∈ V from left to right do if

for each k ∈ N + u do 19:

add vertex r to Γ

21:

end for

22:

end if

23:

Γ * ← GeneratedfromVertices(Γ, V)

C * ← UsedColors(Γ * )

25:

color all vertices in Γ using Color(C * , C) 26: end for 27: V ← GeneratedfromVertices(MaxWeightVertices(V ),V) 28: for each induced vertex ν ∈ V do end if 35: end for 36: return set of vertices in V

Performance Analysis

In this subsection we derive the theoretical performance guarantee of our approximation algorithm. We first prove that all vertices in V are colored by Algorithm 5 in Lemma 5.4. Then, we prove that the set of vertices, from which the vertices of any same color are generated, induces a RIS in Lemma 5.5, and Algorithm 5 outputs a set of vertices mapping to a feasible scheduling policy in Lemma 5.6. We are then able to establish the approximation factor of Algorithm 5 in Theorem 5.2. We conclude this subsection by giving the complexity of Algorithm 5.

Lemma 5.4. All vertices in V are colored by Algorithm 5.

Proof Sketch. We prove that any elementary vertex and any induced vertex is colored by Algorithm 5.

Lemma 5.5. For any color c ∈ C, the set of vertices, from which the vertices colored by c are generated, induces a RIS.

Proof Sketch. We first prove that any pair of vertices colored by c is not generated from a same vertex or any pair of adjacent vertices, indicating that the set of vertices, from which the vertices colored by c are generated, is not adjacent to each other, i.e., the set of vertices satisfies the first property of RIS. For each induced vertex colored by c, let u denote the vertex from which the vertex is generated. We then prove that there is a vertex, which is generated from the parent of u, colored by c, indicating that the set of vertices, from which the vertices colored by c are generated, satisfies the second property of RIS. By combining the above analysis, the set of vertices, from which the vertices colored by c are generated, induces a RIS.

Lemma 5.6. Algorithm 5 outputs a set of vertices that maps to a feasible scheduling policy.

Proof Sketch. By Lemma 5.5, the set of vertices, denoted by V, output by Algorithm 5 is a RIS of G. We prove that the set of vertices in V follows the adapted FIFO model.

It then follows from the definition of feasible scheduling policy that the output of Algorithm 5 maps to a feasible scheduling policy.

Theorem 5.2. Algorithm 5 outputs an asymptotically 1/(D 1 +f max •D 2 )-optimal feasible scheduling policy for the offline scheduling problem, i.e., Algorithm 5 is a 1/(D 1 + f max • D 2 )-approximation algorithm.

Proof Sketch. By Lemma 5.4 and Lemma 5.5, we get at most (D

RISes of G. We prove that there exists a RIS whose total reward is at least 1/(D 1 + f max • D 2 ) of the utility for the optimal feasible scheduling policy. The theorem is thus proved.

Inapproximability

We start by showing that the online problem in its generic form cannot be approximated with any finite competitive ratio.

Theorem 5.3. For any ρ > 0, there exists an instance of our scheduling problem, where the competitive ratio of any deterministic online algorithm Π on the instance is larger than ρ.

Proof. We consider the following instance of our online scheduling problem. In slot 0, request 1 belonging to group 1 with the quadruple (0, 1, 1, 2) arrives, whose reward is 1. We distinguish two cases.

• If Π does not serve the request, then there is no more request arriving, leading to a competitive ratio of infinity as the optimal solution is clearly to serve the request;

• If Π serves the request, a set of requests belonging to group 2 arrives, each characterized by the same quadruple (1, 2l max /l min , F, 2l max /l min ), and the total reward of them is more than ρ. Under this request sequence, the optimum scheduling policy serves the requests belonging to group 2 while Π only serves the request belonging to group 1, leading to a competitive ratio larger than ρ.

Combining the above two cases completes our proof.

Online Scheduling Algorithm Design

Theorem 5.3 establishes the inapproximability of the online case of our scheduling problem in the generic case. By examining the problem instance in Theorem 5.3, we observe that the inapproximability is due to the stringent deadline constraint in the instance. Consequently, any online algorithm is forced to make a decision immediately when the requests arrive. Motivated by this observation, we slightly relax the slackness of the requests, and design an online scheduling algorithm with bounded competitive ratio. Specifically, we assume that the slackness of each request i is at least

We give a high-level overview of our online scheduling algorithm. while Φ = ∅ do 30:

i ← HighestPrioRequest(Φ)

for each request k ∈ Φ do 32: Proof Sketch. Let T denote the set of slots, where each slot t ∈ T satisfies that: (1) Algorithm 6 starts serving at least one request k at slot t, and (2) t is not occupied when Algorithm 6 considers the slot t. We first prove that the utility of the optimal scheduling policy is upper-bounded by the total reward of the requests, each of which • Our algorithms achieve better performance in the first setting. This is because the quantity of contiguous frequency band requested by each user i is f i ≤ F in the first setting while each user requests the whole band in the second setting, indicating that the spectrum resource can be allocated to more users in the first setting.

Scenario 3

In this scenario, we set B = 5, and randomly choose the parameters a i , d i , f i , l i , b i such that 1 ≤ f i ≤ F, ∀i ∈ N . We run the experiments including the following two settings: [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF]

for this scenario are shown in Figure 5.9 and 5.10. From the results, we derive the following observations.

• Our algorithms achieve at least 54% of the optimal utility in offline case, and 43% of the optimal utility in online case.

Appendix

Integer Linear Problem Formulation of Offline Channel Bonding

The offline optimum spectrum bonding problem P4 can be formulated as a network utility maximization (NUM) problem as below.

(5.6e)

(5.6h)

is the allocated spectrum, x i is the decision variable indicating whether to serve user i. Constraints (5.6a)-(5.6d) imply that if the user i cannot be served simultaneously with user j, their allocated spectrum cannot overlap. Constraint (5.6e) implies that if request j is served under the lower priority than the priority under which request i is served, the time to start serving j cannot be earlier that the time to start serving i. Constraints (5.6f) indicates that if request j is served, it must be served under the priority of itself or batched with a request with highest priority among the served users who belong to group b j and whose time-frequency blocks can fit for serving j.

Constraints (5.6g) and (5.6h) are the feasibility constraints in the frequency and time domains.

Table 5.5 lists the additional notations in Appendix.

among the subset of vertices there are two neighboring vertices u and v connected by an edge denoted by e. Recall the construction of graph G:

• e cannot be a type 1 edge, otherwise u and v interfere with each other, contradicting with the fact that the time-frequency blocks that are allocated to any pair of interference users do not overlap.

• e cannot be a type 2 edge, otherwise, u and v violate the FIFO model, contradicting with the fact that any feasible scheduling policy does not not violate the FIFO model.

• e cannot be a type 3 edge, otherwise u and v correspond to the same request, contradicting with the fact that each request is executed at most once at any feasible scheduling policy.

The above analysis demonstrates that e cannot exist, thus proving via contradiction that the subset of vertices maps to an IS of G.

We then prove that the parent of any induced vertex in the subset is also in the subset. Based on the definitions of the feasible policy and the adapted FIFO model, for each request instantiated by an induced vertex in the subset, it must reuse the time-frequency block of a request instantiated by an elementary vertex in the subset.

It follows from the construction of the request graph that the elementary vertex is the parent of the induced.

By combining the above analysis, each feasible policy maps to a RIS of G.

Proof of Lemma 5.2

Before giving the proof of Lemma 5.2, we first prove the following lemma.

Lemma 5.7. For any pair of elementary vertices

holds that at most one of v 1 and v 2 can be chosen at any feasible scheduling policy.

Proof. Assume, by contradiction, that both v 1 and v 2 are chosen at a feasible scheduling policy. We proceed by distinguishing the following two cases.

• Case 1: k 1 = k 2 . v 1 and v 2 instantiate the same request, thus are connected by a type 3 edge.

• Case 2:

follows from the construction of G that v 1 and v 2 are connected by a type 2 edge.

i.e., the request k 2 fits into the time interval and the spectrum corresponding to the vertex v 1 . It then follows from the construction of G that v 1 and v 2 are connected by a type 2 edge.

In both cases, v 1 and v 2 are connected by an edge, contradicting to the fact that any pair of vertices at any feasible scheduling policy is not adjacent to each other. Lemma

b,τ (t, s) and a i ≤ τ, ∀i ∈ N α b,τ (t, s), it then follows from Lemma 5.7 that there is at most one vertex v ∈ V α b,τ (t, s) with l v = l and h v = f at any feasible scheduling policy. Therefore, there are at most (F b -f b + 1) min{L b -l b + 1, L b -(t -τ )} elementary vertices in V α b,τ (t, s) at any feasible scheduling policy.

By summing over (F

the size of elementary vertices in V α (t, s) belonging to group b at any feasible scheduling policy is upper-bounded by

We then prove that the vertices in V α (t, s) at any feasible scheduling policy belong 5.7.6 Proof of Lemma 5.4 We first prove that any elementary vertex in V is colored by Algorithm 5. Consider each elementary vertex v ∈ V and the vertex set Γ v , where let Γ v denote the set of vertices including v to be colored in the iteration of coloring v. We prove that each vertex in Γ v is colored by Algorithm 5 in Lemma 5.8. Let Γ * v denote the set of vertices from which the vertices in Γ v are generated. Lemma 5.8. Each vertex in Γ v is colored by Algorithm 5.

Proof. In the iteration of coloring v, the color that cannot be used to Γ v have been used to color the vertices that are generated from Γ * v and the neighbors of Γ * v . The vertices that are generated from Γ * v and the neighbors of Γ * v can be divided into the following three classes. Let b denote the group to which the request covered by v belongs.

• The first class of vertices generated from the vertices in V that are connected with Γ * v by type 1 edges. When we color the vertices in Γ v , it follows from Step 2 that all elementary vertices r ∈ V with t r < t v have been colored and no elementary vertex r with t r > t v is colored. Therefore, the colors, which cannot be used to Γ v , have been used to color the elementary vertices in

For each (t v , s), s ∈ [s v , s v + h v -1] pair, it follows from the constraint (5.4) that the number of active elementary vertices in V at (t v , s) is upper-bounded by

By summing over the number of D 2 • N active elementary vertices for all (t v , s), s ∈

] pairs. Therefore, the number of colors, which cannot be used to Γ v and which have been used to color all the first class of vertices in the iteration of coloring v, is upper-bounded by

• The second class of vertices generated from the vertices in V that are connected with Γ * v by type 2 edges. For each user k ∈ N , it then follows from constraint (5.5) that

Therefore, the number of elementary vertices generated from the vertices in V c (k) is upper-bounded by D 1 N .

We first note that the current proof is based on that the vertices in V c (k) are adjacent to each other. Clearly, the edges that connect each pair of vertices in V c (k) include all type 2 edges between the vertices in V c (k).

Consider any pair of requests

Based on the construction of G, there is no type 2 edge between any vertex in V c (k 1 )\V c (k 2 ) and any vertex in V c (k 2 )\V c (k 1 ). When Algorithm 5 colors the vertices generated from

Thus, the colors that are used to the vertices generated

if there is also no type 1 and 3 edge. Since for each request k ∈ N , the number of elementary vertices generated from the vertices in V c (k) is at most D 1 N , the number of colors used to the second class of vertices of a same group is upperbounded by D 1 N .

• The third class of vertices generated from Γ * v and the vertices in V that are connected with Γ * v by type 3 edges. For each vertex u ∈ Γ v , let j denote the request covered by u. Based on the definition of V c (j), the elementary vertices in V j belong to V c (j) and the parent of each induced vertex in V j belongs to V j . Thus, any pair of vertices generated from V j are not colored by a same color if the vertices in V c (j) are adjacent to each other. Because we derive the number of colors that are occupied by the second class of vertices based on that the vertices in V c (k), ∀k ∈ N are adjacent to each other, when Algorithm 5 colors Γ v , the colors that have been used to its third class of vertices are considered by the analysis of the second class of vertices. By combining the above analysis, it holds that the number of colors that have been used to the vertices generated from Γ * v and the neighbors of Γ * v is at most (D 1 + f max • D 2 ) N -f max -1. Therefore, the vertices in Γ v is colored by a color in C because of |C| = (D 1 + f max • D 2 ) N -f max . The lemma is thus proved.

simultaneously, but also task dependency, i.e., the dependency among tasks forms a directed acyclic graph. This adds an even stronger combinatorial flavor to the problem and deserves a careful investigation.

Flexible FIFO model

Our works presented in Chapters 3 and 4 focus on the adapted FIFO model illustrated in Figures 4.1 and 5.2, where when any scheduling policy serves user i, any user j > i that requests the packet b i or belongs to group b i must be batched with request i, as long as j can fit into the time interval or time-frequency block of i. In many practical scenarios, admitted requests may be served according to a more flexible FIFO model.

Consider the contiguous-resource batching task scheduling problem. We now consider a flexible FIFO model defined as below. Definition 6.1 (Flexible FIFO model). When any scheduling policy serves request i, any request j > i that belongs to group b i can but does not have to be served simultaneously with request i if j can fit in the service time of i and the spectrum allocated to i.

Note that the flexible FIFO model for the problem of downlink transmission scheduling with data sharing is similar. FIFO models, we consider an example composed of six requests, indexed from 1 to 6, with the corresponding request quadruples (0, 0, F, 1), (0, 1, F, 1), (0, 2, F, 1), (0, 0, F, 1)

and (1, 1, F, 1), (2, 2, F, 1), respectively. Requests 1,2,4 and 5 belong to group 1, and requests 3,6 belongs to group 2. The reward of each request is 1. The rectangles in Figure 6.1 illustrate the possible executions of the requests, with the height being the quantity of requested spectrum and the length being the requested execution time.

• Figure 6.1(a) illustrates the optimal scheduling policy under the flexible FIFO model, which serves requests 1 and 4 at slot 0, requests 2 and 5 at slot 1, requests 3 and 6 at slot 3. Request 2 is not served simultaneously with request 1 at slot 0 in order to serve request 5 at slot 1 under a higher priority.

• Figure 6.1(b) illustrates the optimal scheduling policy under the adapted FIFO model, which serves requests 1,2 and 4 at slot 0, requests 3 and 6 at slot 2, or requests 1,2 and 4 at slot 0, request 5 at slot 1, request 6 at slot 2. Different from the adapted FIFO model, request 2 must be served simultaneously with request 1.

• Figure 6.1(c) illustrates the optimal scheduling policy under the standard FIFO model, which serves requests 1,2 and 4 at slot 0, request 5 at slot 1, request 6 at slot 2. Different from the flexible and adapted FIFO models, any admitted request should be started no later than any admitted request arriving later.

We can check that under flexible FIFO policy, all the six requests are served; under the adapted and standard FIFO models, at most five requests can be served.

The flexible FIFO model is more flexible than the adapted and standard FIFO models and leads to better efficiency. The flexible FIFO model is technically more involved than the adapted and standard FIFO models. Any mathematical framework under the flexible FIFO model can be extended to the adapted and standard FIFO models.

Based on the definition of flexible FIFO model, we expect to seek the optimal scheduling policy maximizing the overall system utility for the problems of downlink transmission scheduling with data sharing and contiguous-resource batching task scheduling. We also expect to seek the optimal scheduling policy minimizing the total delay cost or minimizing makespan for the problems.