Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximizing Online Utilization with Commitment
375
0
0.0
(
0
)
Added by
Uwe Schwiegelshohn
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Chris Schwiegelshohn
Ask ChatGPT about the research
No Arabic abstract
We investigate online scheduling with commitment for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. As soon as a job has been submitted, the commitment constraint forces us to decide immediately whether we accept or reject the job. Upon acceptance of a job, we must complete it before its deadline $d$ that satisfies $d geq (1+epsilon)cdot p + r$, with $p$ and $r$ being the processing time and the submission time of the job, respectively while $epsilon>0$ is the slack of the system. Since the hard case typically arises for near-tight deadlines, we consider $varepsilonleq 1$. We use competitive analysis to evaluate our algorithms. Our first main contribution is a deterministic preemptive online algorithm with an almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound $frac{1+epsilon}{epsilon}$ of the greedy acceptance policy. Then the competitive ratio improves with an increasing number of machines and approaches $(1+epsilon)cdotln frac{1+epsilon}{epsilon}$ as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small $epsilon$. In the non-preemptive case, we present a deterministic algorithm on $m$ machines with a competitive ratio of $1+mcdot left(frac{1+epsilon}{epsilon}right)^{frac{1}{m}}$. This matches the optimal bound of $2+frac{1}{epsilon}$ of the greedy acceptance policy for a single machine while it again guarantees an exponential improvement over the greedy acceptance policy for small $epsilon$ and large $m$. In addition, we determine an almost tight lower bound that approaches $mcdot left(frac{1}{epsilon}right)^{frac{1}{m}}$ for large $m$ and small $epsilon$.
rate research
Read More
Resource allocation problems are a fundamental domain in which to evaluate the fairness properties of algorithms. The trade-offs between fairness and utilization have a long history in this domain. A recent line of work has considered fairness questions for resource allocation when the demands for the resource are distributed across multiple groups and drawn from probability distributions. In such cases, a natural fairness requirement is that individuals from different groups should have (approximately) equal probabilities of receiving the resource. A largely open question in this area has been to bound the gap between the maximum possible utilization of the resource and the maximum possible utilization subject to this fairness condition. Here, we obtain some of the first provable upper bounds on this gap. We obtain an upper bound for arbitrary distributions, as well as much stronger upper bounds for specific families of distributions that are typically used to model levels of demand. In particular, we find - somewhat surprisingly - that there are natural families of distributions (including Exponential and Weibull) for which the gap is non-existent: it is possible to simultaneously achieve maximum utilization and the given notion of fairness. Finally, we show that for power-law distributions, there is a non-trivial gap between the solutions, but this gap can be bounded by a constant factor independent of the parameters of the distribution.
We introduce a new model of computation: the online LOCAL model (OLOCAL). In this model, the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-$T$ neighborhood before choosing the output; instead of looking ahead in time, we have the power of looking around in space. It is natural to compare OLOCAL with the LOCAL model of distributed computing, in which all nodes make decisions simultaneously in parallel based on their radius-$T$ neighborhoods.
In Bipartite Correlation Clustering (BCC) we are given a complete bipartite graph $G$ with `+ and `- edges, and we seek a vertex clustering that maximizes the number of agreements: the number of all `+ edges within clusters plus all `- edges cut across clusters. BCC is known to be NP-hard. We present a novel approximation algorithm for $k$-BCC, a variant of BCC with an upper bound $k$ on the number of clusters. Our algorithm outputs a $k$-clustering that provably achieves a number of agreements within a multiplicative ${(1-delta)}$-factor from the optimal, for any desired accuracy $delta$. It relies on solving a combinatorially constrained bilinear maximization on the bi-adjacency matrix of $G$. It runs in time exponential in $k$ and $delta^{-1}$, but linear in the size of the input. Further, we show that, in the (unconstrained) BCC setting, an ${(1-delta)}$-approximation can be achieved by $O(delta^{-1})$ clusters regardless of the size of the graph. In turn, our $k$-BCC algorithm implies an Efficient PTAS for the BCC objective of maximizing agreements.
The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ items of different sizes in the range $(0,1]$; a bin is said to be covered if it receives items of total size at least 1. We study this problem in the advice setting and provide tight bounds for the size of advice required to achieve optimal solutions. Moreover, we show that any algorithm with advice of size $o(log log n)$ has a competitive ratio of at most 0.5. In other words, advice of size $o(log log n)$ is useless for improving the competitive ratio of 0.5, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size $O(log log n)$ is sufficient to achieve a competitive ratio that is arbitrarily close to $0.53bar{3}$ and hence strictly better than the best ratio $0.5$ attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems. Finally, we show that a linear number of bits of advice is necessary to achieve any competitive ratio better than 15/16 for the online bin covering problem.
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the clients location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log n_act / log log n_act)-competitive algorithm, where n_act is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log n/ log log n), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log m + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where m is number of points in the input metric and c is the capacity of any open facility.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
