Consider a platform where independent agents arrive at random times and need to be matched into pairs, eventually after waiting for some time. This, for example, models job markets, gaming platforms, kidney exchange programs, etc. The platform decides how to match agents together while optimizing two conflicting objectives: the quality of the matching produced, and the total waiting time of the agents. This can be modeled as an online problem called Min-cost Perfect Matching with Delays (MPMD). In the case when agents arrive in an adversarial order, no online algorithm can achieve a constant-competitive ratio. In this paper, we study a realistic case where agents’ arrival times follow some stochastic assumptions, and we present two matching mechanisms, which give constant-competitive solutions. The first one is a simple greedy algorithm in which agents act in a distributed manner requiring only local communication. The second one builds global analysis tools in order to obtain even better performance guarantees. This result is surprising as the greedy approach cannot achieve a competitive ratio better than $$O(m^{\log 1.5 + \varepsilon })$$ in the adversarial model, where m denotes the number of agents. Finally, we extend our results to the general delay cost case, the clearing requests with penalty case, and the asymmetric distance case.

This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. In this problem, we are given an edge-weighted rooted tree $T$, and we have to serve a sequence of requests arriving at its vertices in an online manner. Each request $r$ is characterized by two parameters: its arrival time $t(r)$ and location $l(r)$ (a vertex). Once a request $r$ arrives, we can either serve it immediately or postpone this action until any time $t > t(r)$. We can serve several pending requests at the same time, and the service cost of a service corresponds to the weight of the subtree that contains all the requests served and the root of $T$. Postponing the service of a request $r$ to time $t > t(r)$ generates an additional delay cost of $t - t(r)$. The goal is to serve all requests in an online manner such that the total cost (i.e., the total sum of service and delay costs) is minimized. The current best algorithm for this problem achieves a competitive ratio of $O(d^2)$ (Azar and Touitou, FOCS'19), where $d$ denotes the depth of the tree. Here, we consider a stochastic version of MLA where the requests follow a Poisson arrival process. We present a deterministic online algorithm which achieves a constant ratio of expectations, meaning that the ratio between the expected costs of the solution generated by our algorithm and the optimal offline solution is bounded by a constant. Our algorithm is obtained by carefully combining two strategies. In the first one, we plan periodic oblivious visits to the subset of frequent vertices, whereas in the second one, we greedily serve the pending requests in the remaining vertices. This problem is complex enough to demonstrate a very rare phenomenon that ``single-minded" or ``sample-average" strategies are not enough in stochastic optimization.

We consider two combinatorial optimization problems, named Generalized Skyline Interval Coloring (GSIC) and Dynamic Geometric Bin Packing (DGBP). The input to both problems is a set of interval jobs, with each job specified by a horizontal active time interval and a vertical size. For GSIC, each job is to be allocated a vertical interval of the specified size in the range [0, +∞). For any two jobs with overlapping active intervals, their vertical intervals must not overlap. The instantaneous cost of an allocation at any time is defined as the highest point allocated to the active jobs. The target is to minimize the accumulated cost over time. For DGBP, each job is to be assigned to a machine of capacity g and be allocated a vertical interval of the specified size in the range [0, g). For any two jobs with overlapping active intervals, if they are assigned to the same machine, their vertical intervals must not overlap. The target is to minimize the total machine busy time, where the busy time of a machine is the time duration in which there is at least one active job in the machine. We develop O(1)-approximation algorithms for both problems in the offline setting and asymptotically optimal algorithms in the non-clairvoyant and clairvoyant online settings.

We consider the problem of online min-cost perfect matching with concave delays. We begin with the single location variant. Specifically, requests arrive in an online fashion at a single location. The algorithm must then choose between matching a pair of requests or delaying them to be matched later on. The cost is defined by a concave function on the delay. Given linear or even convex delay functions, matching any two available requests is trivially optimal. However, this does not extend to concave delays. We solve this by providing an O(1)-competitive algorithm that is defined through a series of delay counters. Thereafter we consider the problem given an underlying n-points metric. The cost of a matching is then defined as the connection cost (as defined by the metric) plus the delay cost. Given linear delays, this problem was introduced by Emek et al. and dubbed the Min-cost perfect matching with linear delays (MPMD) problem. Liu et al. considered convex delays and subsequently asked whether there exists a solution with small competitive ratio given concave delays. We show this to be true by extending our single location algorithm and proving O(log n) competitiveness. Finally, we turn our focus to the bichromatic case, wherein requests have polarities and only opposite polarities may be matched. We show how to alter our former algorithms to again achieve O(1) and O(log n) competitiveness for the single location and for the metric case.

We study a busy-time scheduling problem on heterogeneous machines (BSHM) which is motivated by server acquisition and task dispatching in cloud computing. The input of BSHM is a set of interval jobs, each specified by a size, an arrival time and a departure time. When a job arrives, it must be placed onto a machine immediately. The execution of a job cannot be interrupted until it departs. At any time, the total size of the jobs running on a machine cannot exceed the machine's capacity. m different types of machines are available and abundant machines are provided for each type. A type-i machine has a capacity giand is charged at a cost rate riwhen busy (running jobs). The target of BSHM is to schedule the given set of jobs onto machines with the minimum accumulated cost. Suppose the machine types are sorted by their capacities so that g1g2≤ ⋯ ≤ gm. We first consider two typical cases of BSHM. In BSHM-DEC, ri/gi≥ ri+1/gi+1holds for each i. In BSHM-INC, ri/gi≤ ri+1/gi+1holds for each i. For each case, we propose a O(1)-approximation algorithm in the offline setting and a O(μ)-competitive algorithm in the nonclairvoyant online setting. Finally, we discuss how the scheduling strategies developed for these two cases can be combined to deal with the general BSHM problem.

We study an interval job scheduling problem in distributed systems. We are given a set of interval jobs, with each job specified by a size, an arrival time and a processing length. Once a job arrives, it must be placed on a machine immediately and run for a period of its processing length without interruption. The homogeneous machines to run jobs have the same capacity limits such that at anytime, the total size of the jobs running on any machine cannot exceed its capacity. Launching each machine incurs a fixed cost. After launch, a machine is charged a constant cost per time unit until it is terminated. The problem targets to minimize the total cost incurred by the machines for processing the given set of interval jobs. We focus on the algorithmic aspects of the problem in this article. For the special case where all the jobs have a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we propose a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a O(μ)-competitive Modified First-Fit algorithm which is near optimal (μ is the max/min job processing length ratio). In the clairvoyant online setting, we propose an asymptotically optimal O(√log μ)-competitive algorithm based on our Modified First-Fit strategy.

We consider a scheduling problem for running jobs on machines rented from the cloud. Cloud service providers such as Amazon EC2 and Google Cloud offer machines to rent on demand, and charge the rental usage by a specific interval of time, say at an hourly rate. This pricing model creates an interesting optimization problem called Interval Scheduling with Discrete Charging Units (ISDCU) which assigns jobs to run on the machines with the objective of minimizing the rental cost. In this paper, we study the problem of ISDCU where each machine can process a maximum of g jobs simultaneously. We focus on interval jobs where each job must be assigned to a machine upon its arrival and run for a required processing length. We show that ISDCU is NP-hard even for the case of g = 1. We also show that no deterministic online algorithm can achieve a competitive ratio better than max{2, g} in the non-clairvoyant setting, and better than max{3/2, g} in the clairvoyant setting. Lastly, we develop and analyze several online algorithms, most of which achieve a competitive ratio of O(g).

In this paper, we study an online Flexible Job Scheduling (FJS) problem. The input of the problem is a set of jobs, each having an arrival time, a starting deadline and a processing length. Each job has to be started by the scheduler between its arrival and its starting deadline. Once started, the job runs for a period of the processing length without interruption. The target is to minimize the span of all the jobs --- the time duration in which at least one job is running. We study online FJS under both the non-clairvoyant and clairvoyant settings. In the non-clairvoyant setting, the processing length of each job is not known for scheduling purposes. We first establish a lower bound of μ on the competitive ratio of any deterministic online scheduler, where μ is the max/min job processing length ratio. Then, we propose two O(μ)-competitive schedulers: Batch and Batch+. The Batch+ scheduler is proved to have a tight competitive ratio of (μ+1). In the clairvoyant setting, the processing length of each job is known at its arrival and can be used for scheduling purposes. We establish a lower bound of (√5+1)/2 on the competitive ratio of any deterministic online scheduler, and propose two O(1)-competitive schedulers: Classify-by-Duration Batch+ and Profit. The Profit scheduler can achieve a competitive ratio of 4+2√2. Our work lays the foundation for extending several online job scheduling problems in cloud and energy-efficient computing to jobs that have laxity in starting.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by “pay-as-you-go” billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of μ + 3 on the competitive ratio of the commonly used First Fit packing algorithm, where μ is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by "pay-as-you-go" billing. The above job dispatching problem can be modeled as a variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP. In this paper, we develop new approaches to the competitive analysis of the commonly used First Fit packing algorithm for the MinUsageTime DBP problem, and establish a new upper bound of μ+4 on the competitive ratio of First Fit packing, where μ is the ratio of the maximum job duration to the minimum job duration. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

The MinUsageTime Dynamic Bin Packing (DBP) problem targets at minimizing the accumulated usage time of all the bins in the packing process. It models the server acquisition and job scheduling issues in many cloud-based systems. Earlier work has studied MinUsageTime DBP in the non-clairvoyant setting where the departure time of each item is not known at the time of its arrival. In this paper, we investigate MinUsageTime DBP in the clairvoyant setting where the departure time of each item is known for packing purposes. We study both the offline and online versions of Clairvoyant MinUsageTime DBP. We present two approximation algorithms for the offline problem, including a 5-approximation Duration Descending First Fit algorithm and a 4-approximation Dual Coloring algorithm. For the online problem, we establish a lower bound of 1+√5/2 on the competitive ratio of any online packing algorithm. We propose two strategies of item classification for online packing, including a classify-by-departure-time strategy and a classify-by-duration strategy. We analyze the competitiveness of these strategies when they are applied to the classical First Fit packing algorithm. It is shown that both strategies can substantially reduce the competitive ratio for Clairvoyant MinUsageTime DBP compared to the original First Fit algorithm.