Regular ArticleThe Competitiveness of On-Line Assignments
Abstract
Consider the on-line problem, where a number of servers are ready to provide service to a set of customers. Each customer′s job can be handled by any of a subset of the servers. Customers arrive one by one and the problem is to assign each customer to an appropriate server in a manner that will balance the load on the servers. This problem can be modeled in a natural way by a bipartite graph where the vertices of one side (customers) appear one at a time and the vertices of the other side (servers) are known in advance. We derive tight bounds on the competitive ratio in both deterministic and randomized cases. Let n denote the number of servers. In the deterministic case we provide an on-line algorithm that achieves a competitive ratio of k = [log2n] (up to an additive 1) and prove that this is the best competitive ratio that can be achieved by any deterministic on-line algorithm. In a similar way we prove that the competitive ratio for the randomized case is k′ = ln(n) (up to an additive 1). We conclude that for this problem, randomized algorithms differ from deterministic ones by precisely a constant factor.
References (0)
Cited by (143)
Online fractional hierarchical scheduling on uniformly related machines
2020, Computers and Operations ResearchThis paper studies the online fractional hierarchical scheduling problem on uniformly related machines. In the problem, the jobs and machines have several different hierarchies and a job can be processed on a machine if and only if its hierarchy is not below the hierarchy of the machine, furthermore, the jobs can be arbitrarily split between the machines. The objective is to determine the assignment scheme of the jobs so as to minimize the makespan. We present several sophisticated lower bounds and an online algorithm framework for the problem. Our bounds dominate all known bounds, and the algorithm is optimal for the problem with no more than four hierarchies. Computational tests show that our algorithm has the potential to work for all cases.
Robust two-stage packing into designated and multipurpose bins
2019, IFAC-PapersOnLineMultitype bin packing is a natural extension of the classical bin packing with applications to shipping using climate-controlled containers and plain dry containers. In transportation and other logistics applications there may be significant uncertainty with respect to the exact quantities of different variants of products (or item types) that may need to be shipped at the time when the containers and packaging are procured. In the current paper we model the problem as a robust two-stage two-item type bin packing problem. In the first stage bins of different types are acquired (e.g., reefer containers and dry containers). In the second stage the items are packed into bins. The bins that are secured in the first phase must allow for all of the items to be packed in the “worst-case” demand scenario. We first develop an algorithm for the robust two-stage two-item type bin packing problem with general item-number uncertainty sets and certain box uncertainty sets for item sizes (or equivalently two item sizes). We then consider the special case of identical (or unit) item sizes. In this special case we develop closed-form solutions for the optimal solution. Our closed-form solution reveals that it is optimal to use a number of multipurpose bins that is linear in the number of items. This is in contrast with solutions of the online and offline deterministic version of our problem that use at most one multipurpose bin. Finally, we consider computational methods that are efficient in practice for a generalization with unit item sizes but with an arbitrary number of item and bin types and arbitrary compatibility structures.
Rejecting jobs to minimize load and maximum flow-time
2018, Journal of Computer and System SciencesThe notion of competitive ratio often turns out to be too pessimistic for the analysis of online algorithms. Although the approach of resource augmentation (introduced by Kalyanasundaram and Pruhs) has been very successful in dealing with a variety of objective functions, there are problems for which even a (arbitrary) constant speedup cannot lead to a constant competitive algorithm. Here we propose a rejection model which permits the online algorithm to not serve epsilon-fraction of requests. We present and -competitive algorithms for the problems of load balancing and minimizing maximum flow time in the restricted assignment setting.
Multiprofessor scheduling
2018, Discrete Applied MathematicsWe introduce a new model called “Multiprofessor Scheduling”. This problem is a generalization of a number of previous models. On a set of professors and a set of lectures (with given, equal or different durations), a problem instance is specified by two kinds and of conditions given with a list of pairs in the following way: means that professor can deliver lecture if it is assigned to him, while means that has to be present when is delivered (by any other professor who will deliver the lecture). The optimization problem asks for the shortest possible time within which all lectures can be delivered.
In this paper we take the first steps to study the problem. We restrict our investigations here to the offline setting, i.e. all information about the problem instance is given in advance. We consider mainly the case where all lectures have unit length. For this special case we prove that the optimum value together with an optimal schedule can be determined in polynomial time as a function of if is fixed, or in time linear in if is fixed; but is NP-complete if both and are unbounded, even in the restricted case where each lecture can be given by just one specific professor (i.e., when ) and any other (with index in the range ) is involved in only two conditions of .
We also consider the case of different durations, where the durations are between 1 and for some integer . For this special case we give a polynomial-time approximation algorithm with approximation ratio .
The paper mostly deals with non-preemptive scheduling, but the preemptive scenario is also considered to some extent. Moreover, we introduce and study a third variant that we call interruptive scheduling. It is more restricted than preemptive, and less restricted than non-preemptive.
A General Framework for Learning-Augmented Online Allocation
2023, Leibniz International Proceedings in Informatics, LIPIcs