1,721,124 research outputs found
Semi-clairvoyant scheduling
No full textWe continue the investigation initiated in [2] of the quality of service (QoS) that is achievable by semi-clairvoyant online scheduling algorithms, which are algorithms that only require approximate knowledge of the initial processing time of each job, on a single machine. In [2] it is shown that the obvious semi-clairvoyant generalization of the Shortest Processing Time is O(1)-competitive with respect to average stretch on a single machine. In [2] it was left as an open question whether it was possible for a semi-clairvoyant algorithm to be O(1)-competitive with respect to average flow time on one single machine. Here we settle this open question by giving a semi-clairvoyant algorithm that is O(1)-competitive with respect to average flow time on one single machine. We also show a semi-clairvoyant algorithm on parallel machines that achieves up to contant factors the best known competitive ratio for clairvoyant on-line algorithms. In some sense one might conclude from this that the QoS achievable by semi-clairvoyant algorithms is competitive with clairvoyant algorithms. It is known that the clairvoyant algorithm SRPT is optimal with respect to average flow time and is 2-competitive with respect to average stretch. Thus it is possible for a clairvoyant algorithm to be simultaneously competitive in both average flow time and average stretch. In contrast we show that no semi-clairvoyant algorithm can be simultaneously O(1)-competitive with respect to average stretch and O(1)-competitive with respect to average flow time. Thus in this sense one might conclude that the QoS achievable by semi-clairvoyant algorithms is not competitive with clairvoyant algorithms
Online weighted flow time and deadline scheduling
No full textIn this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P | ri, pmtn | ∑ wi Fi. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling. © 2005 Elsevier B.V. All rights reserved
Stochastic Scheduling of Heavy-tailed Jobs
Full text linkWe revisit the classical stochastic scheduling problem of nonpreemptively scheduling n jobs so as to minimize total completion time on m identical machines, P \mid \mid \mathbb{E} \sum C_j in the standard 3-field scheduling notation. Previously it was only known how to obtain reasonable approximation if jobs sizes have low variability. However, distributions commonly arising in practice have high variability, and the upper bounds on the approximation ratio for the previous algorithms for such distributions can be even inverse-polynomial in the maximum possible job size. We start by showing that
the natural list scheduling algorithm Shortest Expected Processing Time (SEPT) has a bad approximation ratio for high variability jobs. We observe that a simple randomized rounding of a natural linear programming relaxation is a (1+\epsilon)-machine O(1)-approximation assuming the number of machines is at least logarithmic in the number of jobs. Turning to the case of a modest number of machines, we develop a list scheduling algorithm that is O(\log^2 n + m \log n)-approximate. Our results together imply a (1+\epsilon)-machine O(\log^2 n )-approximation for an arbitrary number of machines. Intuitively our list scheduling algorithm finds an ordering that not only takes the expected size of a job into account, but also takes into account the probability that job will be big
Front Matter, Table of Contents, Preface, Programm Commitees, External Reviewers
No full textFront Matter, Table of Contents, Preface, Programm Commitees, External Reviewer
Scalably Scheduling Processes with Arbitrary Speedup Curves
Full text linkWe give a scalable ((1+\epsilon)-speed O(1)-competitive) nonclairvoyant algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time
07261 Summary – Fair Division
Full text linkThe problem of fair division – dividing goods or "bads" (e.g., costs) among entities
in an impartial and equitable way – is one of the most important problems that society
faces. A Google search on the phrase "fair allocation" returns over 100K links, referring
to the division of sports tickets, health resources, computer networking resources, voting
power, intellectual property licenses, costs of environmental improvements, etc
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
