We consider the online scheduling of equal-length jobs with incompatible families on m identical batch machines. Each job has a release time, a deadline and a weight. Each batch machine can process up to b jobs (which...
详细信息
We consider the online scheduling of equal-length jobs with incompatible families on m identical batch machines. Each job has a release time, a deadline and a weight. Each batch machine can process up to b jobs (which come from the same family) simultaneously as a batch, where b is called the capacity of the machines. Our goal is to determine a preemption-restart schedule which maximizes the weighted number of early jobs. For this problem, Li et al. (Inf Process Lett 112:503-508, 2012) provided an online algorithm of competitive ratio 3+2 root 2 for both b = infinity and b < infinity. In this paper, we study two special cases of this problem. For the case that m = 2, we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3 for both b = infinity and b < infinity. For the case in which m = 3, b = infinity and all jobs come from a common family, we present an online algorithm with a competitive ratio of (8 + 2 root 15)/3 approximate to 5.249.
It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to m...
详细信息
It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r (j) ,pmtn|L-max). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.
online streaming algorithms, tailored for continuous data processing, offer substantial benefits but are often more intricate to design than their offline counterparts. This paper introduces a novel approach for autom...
详细信息
online streaming algorithms, tailored for continuous data processing, offer substantial benefits but are often more intricate to design than their offline counterparts. This paper introduces a novel approach for automatically synthesizing online streaming algorithms from their offline versions. In particular, we propose a novel methodology, based on the notion of relational function signature (RFS), for deriving an online algorithm given its offline version. Then, we propose a concrete synthesis algorithm that is an instantiation of the proposed methodology. Our algorithm uses the RFS to decompose the synthesis problem into a set of independent subtasks and uses a combination of symbolic reasoning and search to solve each subproblem. We implement the proposed technique in a new tool called Opera and evaluate it on over 50 tasks spanning two domains: statistical computations and online auctions. Our results show that Opera can automatically derive the online version of the original algorithm for 98% of the tasks. Our experiments also demonstrate that Opera significantly outperforms alternative approaches, including adaptations of SyGuS solvers to this problem as well as two of Opera's own ablations.
We focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request s...
详细信息
We focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request sequences for which all algorithms perform equally poorly. The motivations for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. To utilize these features, the operating system needs to identify data streams that can benefit from more resources. Our approach in this work is based on the relation between entropy, compression, and gambling, extensively studied in information theory. It has been shown that in some settings, entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. Our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. We study bounds based on entropy for three classical online problems-list accessing, prefetching, and caching. Our bounds relate the performance of the best online algorithm to the entropy, a parameter intrinsic to characteristics of the request sequence. This is in contrast to the competitive ratio parameter of competitive analysis, which quantifies the performance of the online algorithm with respect to an optimal offline algorithm. For the prefetching problem, we give explicit upper and lower bounds for the performance of the best prefetching algorithm in terms of the entropy of the request sequence. In contrast, we show that the entropy of the request sequence alone does not fully capture the performance of online list accessing and caching algorithms.
An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, ...
详细信息
An online algorithm must make decisions immediately and irrevocably based only on a part of the input without any knowledge of the future part of the input. We introduce the competitive analysis of online algorithms, a standard worst-case analysis, and present main results of this analysis on the problem of online Bin Packing and on some of its variants. In Bin Packing, a sequence of items of size up to 1 arrives to be packed into the minimal number of unit capacity bins. Mainly, we focus on Colored Bin Packing in which items have also a color and we cannot pack two items of the same color adjacently in a bin. For Colored Bin Packing, we improve some previous results on the problem with two colors and present the first results for arbitrarily many colors. Most notably, in the important case when all items have size zero, we give an optimal 1.5-competitive algorithm. For items of arbitrary size we present a lower bound of 2.5 and a 3.5-competitive algorithm. Powered by TCPDF (***)
online computation is a well-known area of computer science. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexit...
详细信息
online computation is a well-known area of computer science. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexity. We start with exploring a model with restricted memory and show that quantum online algorithms can be better than classical ones (deterministic or randomized) for sublogarithmic space (memory), and they can be better than deterministic online algorithms without restriction for memory. Additionally, we consider the polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well. Another point of view to the online algorithms model is advice complexity. So, we introduce quantum online algorithms with a quantum channel with an adviser. Firstly, we show that quantum algorithms have at least the same computational power as classical ones have. We give some examples of quantum online algorithms with advice. Secondly, we show that if we allow to use shared entangled qubits (EPR-pairs), then a quantum online algorithm can use half as many advise qubits compared to a classical one. We apply this approach to the well-known Paging Problem.
We describe an automata-theoretic approach for the competitive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in R->= 0. By relating the "unbo...
详细信息
ISBN:
(纸本)9780898716801
We describe an automata-theoretic approach for the competitive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in R->= 0. By relating the "unbounded look ahead" of optimal offline algorithms with nondeterminism, and relating the "no look ahead" of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about determinization and approximated determinization of weighted automata.
By offloading the control plane to powerful computing platforms running on commodity hardware, Software Defined Networking (SDN) unleashes the potential to operate computation intensive machine learning tools and solv...
详细信息
ISBN:
(纸本)9781509002238
By offloading the control plane to powerful computing platforms running on commodity hardware, Software Defined Networking (SDN) unleashes the potential to operate computation intensive machine learning tools and solve complex optimization problems in a centralized fashion. This paper studies such an opportunity under the framework of the centralized SDN Admission Control (AC) problem. We first review and adapt some of the key AC algorithms from the literature, and evaluate their performance under realistic settings. We then propose to take a step further and build an AC meta-algorithm that is able to track the best AC algorithm under unknown traffic conditions. To this aim, we exploit a machine learning technique called Strategic Expert meta-Algorithm (SEA).
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which ...
详细信息
ISBN:
(纸本)9783642291159
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines;the completion time of a machine is the sum of the processing times of jobs assigned to it divided by its speed. The objective is to minimize the maximal completion time. The jobs arrive one by one and each has to be assigned to one machine immediately and irrevocably without the knowledge of the future jobs. We prove a new lower bound of 2.564 on the competitive ratio of deterministic online algorithms for this problem, improving the previous lower bound of 2.438.
暂无评论