NDLI: Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Please wait, while we are loading the content...

Clustering to minimize the sum of cluster diameters

Approximating min-sum k-clustering in metric spaces

Local search heuristic for k-median and facility location problems

Profit-earning facility location

One-dimensional quantum walks

Quantum walks on graphs

Quantum algorithms for solvable groups

Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Minimax parametric optimization problems and multi-dimensional parametric searching

Algorithms for minimizing weighted flow time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Stackelberg scheduling strategies

Quantum computers that can be simulated classically in polynomial time

Interaction in quantum communication and the complexity of set disjointness

A new protocol and lower bounds for quantum coin flipping

Loss-less condensers, unbalanced expanders, and extractors

Conditions on input vectors for consensus solvability in asynchronous distributed systems

Spatial gossip and resource location protocols

(1 + εΒ)-spanner constructions for general graphs

Approximate distance oracles

Extractor codes

Excellent codes from modular curves

Sparse polynomial approximation in finite fields

Randomness efficient identity testing of multivariate polynomials

Fully-dynamic min-cut

Computing crossing numbers in quadratic time

Euler paths in series parallel graphs

Decidability of string graphs

Learning mixtures of arbitrary gaussians

Learning DNF in time

Sampling algorithms: lower bounds and applications

Testing metric properties

Testing of matrix properties

Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

One line and ε

A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

Lower bounds for intersection searching and fractional cascading in higher dimension

Sharp threshold and scaling window for the integer partitioning problem

A sharp threshold in proof complexity

Regular resolution lower bounds for the weak pigeonhole principle

The complexity of analytic tableaux

Applications of approximation algorithms to cooperative games

Approximation algorithms for constrained for constrained node weighted steiner tree problems

A constant factor approximation for the single sink edge installation problems

Provisioning a virtual private network: a network design problem for multicommodity flow

Explicit lower bound of 4.5n - o(n) for boolena circuits

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

A read-once branching program lower bound of $Ω(2^{n/4})$ for integer multiplication using universal hashing

On the cell probe complexity of membership and perfect hashing

On the integrality ratio of semidefinite relaxations of MAX CUT

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

Non-approximability results for optimization problems on bounded degree instances

Colouring graphs when the number of colours is nearly the maximum degree

Data-streams and histograms

Optimal static range reporting in one dimension

Biased dictionaries with fast insert/deletes

Anti-persistence: history independent data structures

Dynamic TCP acknowledgement and other stories about e/(e-1)

The price of selfish routing

Buffer overflow management in QoS switches

Almost optimal permutation routing on hypercubes

Online server allocation in a server farm via benefit task systems

Private approximation of NP-hard functions

Concurrent and resettable zero-knowledge in poly-loalgorithm rounds

Black-box concurrent zero-knowledge requires \tilde {Ω} (logn) rounds

The round complexity of verifiable secret sharing and secure multicast

Communication preserving protocols for secure function evaluation

Some perspectives on computational complexity

A sieve algorithm for the shortest lattice vector problem

Fast computation of low rank matrix approximations

Spectral analysis of data

Optimal outlier removal in high-dimensional

Estimating true evolutionary distances between genomes

On optimal slicing of parallel programs

When is the evaluation of conjunctive queries tractable?

The complexity of maximal constraint languages

Quantitative solution of omega-regular games380872

Distribution functions of probabilistic automata

Compatible sequences and a slow Winkler percolation

Edge isoperimetry and rapid mixing on matroids and geometric Markov chains

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

Computing with continuous-time Liapunov systems

Complex tilings

Running time and program size for self-assembled squares

Algorithms, games, and the internet

Automata, circuits and hybrids: facets of continuous time

Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines

Content Provider	ACM Digital Library
Author	Leonardi, Stefano Becchetti, Luca
Abstract	Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, i.e. the average time spent by jobs in the system between release and completion.The Windows NT and the Unix operating system scheduling policies are based on the Multi-level Feedback algorithm [12, 1]. In this paper we prove that a randomized version of the Multi-level Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has been very effective in practice along the last two decades.The randomized Multi-level Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs [7] for a single machine achieving an O(\log n \log\log n) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where n is the number of jobs that are released. We present a version of RMLF working for any numberm of parallel machines. We show for RMLF a first O(\log n\log \frac{n}{m}) competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight O(\log n) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound of [10].
Starting Page	94
Ending Page	103
Page Count	10
File Format	PDF
ISBN	1581133499
DOI	10.1145/380752.380782
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-07-06
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in