Improved Bounds for the Online Scheduling Problem

Johan Rudin,R. Chandrasekaran

Published 2003 in SIAM journal on computing (Print)

ABSTRACT

No abstract is available for this paper.

PUBLICATION RECORD

Publication year
2003
Venue
SIAM journal on computing (Print)
Publication date
2003-03-01
Fields of study
Computer Science
Identifiers
DOI 10.1137/S0097539702403438
External record
Open on Semantic Scholar
Source metadata
Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

No claims are published for this paper.

CONCEPTS

No concepts are published for this paper.

REFERENCES

New lower and upper bounds for on-line scheduling
1994cited by this paper
A better algorithm for an ancient scheduling problem
1994cited by this paper
A Better Lower Bound for On-Line Scheduling
1994influential reference
An On-Line Scheduling Heuristic With Better Worst Case Ratio Than Graham's List Scheduling
1993cited by this paper
New algorithms for an ancient scheduling problem
1992cited by this paper
On the performance of on-line algorithms for partition problems
1989influential reference
Bounds for certain multiprocessing anomalies
1966cited by this paper

CITED BY

Lower bounds for online scheduling on four processors
2025cites this paper
Online Makespan Scheduling under Scenarios
2025cites this paper
Online MMS Allocation for Chores
2025cites this paper
Fifty years of research in scheduling - Theory and applications
2025cites this paper
Semi-online scheduling with non-increasing job sizes and a buffer
2025cites this paper
Improved online load balancing with known makespan
2024cites this paper
How to Balance the Load Online When Jobs and Machines Are Both Selfish?
2024cites this paper
Efficient Task-Network Scheduling With Task Conflict Metric in Time-Sensitive Networking
2024cites this paper
Online Makespan Minimization: Beat LPT by Dynamic Locking
2023cites this paper
Online load balancing with general reassignment cost
2022cites this paper
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
2022cites this paper
Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
2022cites this paper
Online List Scheduling for Makespan Minimization
2022cites this paper
Parallel solutions for preemptive makespan scheduling on two identical machines
2022cites this paper
Online Optimization
2020cites this paper
Online Scheduling with Makespan Minimization: State of the Art Results, Research Challenges and Open Problems
2020cites this paper
Scheduling in the Random-Order Model
2020cites this paper
New Competitive Analysis Results of Online List Scheduling Algorithm
2019cites this paper
A Polynomial Time Algorithm for Scheduling on Processing Time Constraints
2019cites this paper
Online Makespan Minimization: The Power of Restart
2018cites this paper
A survey on makespan minimization in semi-online environments
2018cites this paper
Online scheduling of jobs with favorite machines
2018cites this paper
Improved lower bounds for online scheduling to minimize total stretch
2018cites this paper
Makespan Minimization : The Power of Restart 1
2018cites this paper
Online Makespan Scheduling with Job Migration on Uniform Machines
2018cites this paper
On-Line Load Balancing with Task Buffer
2017cites this paper
Simultaneously Load Balancing for Every p-norm, With Reassignments
2017cites this paper
Truthful Channel Sharing for Self Coexistence of Overlapping Medical Body Area Networks
2016cites this paper
Robust Polynomial-Time Approximation Schemes for Parallel Machine Scheduling with Job Arrivals and Departures
2016cites this paper
Improved lower bounds for the online bin stretching problem
2016cites this paper
Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming
2015cites this paper
Datacenter-Network-Aware Online Load Balancing in MapReduce
2015cites this paper
Pseudo lower bounds for online parallel machine scheduling
2015cites this paper
Lower and upper bounds for online algorithms with advice
2014cites this paper
Maintaining Assignments Online: Matching, Scheduling, and Flows
2014cites this paper
Online load balancing for MapReduce with skewed data input
2014cites this paper
Online scheduling of two job types on a set of multipurpose machines
2014cites this paper
High-multiplicity Scheduling and Packing Problems : Theory and Applications
2014cites this paper
High-Multiplicity Scheduling and Packing Problems
2014cites this paper
Two competitive ratio approximation schemes for a classical scheduling problem
2014cites this paper
An on-line scheduling problem of parallel machines with common maintenance time
2013cites this paper
Online Balancing Two Independent Criteria upon Placements and Deletions
2013cites this paper
Online Makespan Minimization with Parallel Schedules
2013cites this paper
Modeling and constructing unstructured overlay networks: Algorithms, techniques and the Smart Grid case
2013cites this paper
Competitive-Ratio Approximation Schemes for Minimizing the Makespan in the Online-List Model
2013cites this paper
Online algorithms with advice for bin packing and scheduling problems
2013influential citation
Approximating the optimal competitive ratio for an ancient online scheduling problem
2013cites this paper
Automata, Languages, and Programming
2013cites this paper
An on-line scheduling problem of parallel machines with common maintenance time
2013cites this paper
Improved semi-online makespan scheduling with a reordering buffer
2013influential citation
On semi-online machine scheduling and generalized bin covering
2013influential citation
Semi-online scheduling problems on a small number of machines
2013cites this paper
Recent Advances for a Classical Scheduling Problem
2013cites this paper
Online Frequency Allocation and Mechanism Design for Cognitive Radio Wireless Networks
2013cites this paper
Online and Semi-online Scheduling
2013cites this paper
Approximation Algorithms for Multi-processor Task Scheduling Problems on Identical Parallel Processors
2013cites this paper
On Semi-Online Machine Scheduling and Generalized Bin Covering
2013cites this paper
Computing Lower Bounds for Semi-Online Optimization Problems: Application to the Bin Stretching
2013cites this paper
Online Scheduling with Migration Cost
2012cites this paper
Online Minimum makespan Scheduling with a Buffer
2012cites this paper
SIGACT news online algorithms column 21: APPROX and ALGO
2012cites this paper
Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs
2012cites this paper
An overview of some results for reordering buffers
2012cites this paper
Online Bounds on Balancing Two Independent Criteria with Replication and Reallocation
2012cites this paper
A Semi-on-Line Scheduling Problem of Two Parallel Machines with Common Maintenance Time
2012cites this paper
D-factor: a quantitative model of application slow-down in multi-resource shared systems
2012cites this paper
Rotating Escalators upon Deletions for Improving Online Bicriteria Load Balancing
2012influential citation
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
2012cites this paper
A New Approach to Online Scheduling
2012cites this paper
Online scheduling of two job types on a set of multipurpose machines with unit processing times
2012cites this paper
Semi-online scheduling revisited
2012cites this paper
Lower bounds for online makespan minimization on a small number of related machines
2012cites this paper
Competitive-Ratio Approximation Schemes for Makespan Scheduling Problems
2012cites this paper
On the optimality of list scheduling for online uniform machines scheduling
2012cites this paper
The Power of Recourse in Online Optimization: Robust Solutions for Scheduling, Matroid and MST Problems
2012influential citation
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
2011influential citation
TOFU: Semi-Truthful Online Frequency Allocation Mechanism for Wireless Networks
2011cites this paper
Scheduling unit length jobs on parallel machines with lookahead information
2011cites this paper
On the Value of Job Migration in Online Makespan Minimization
2011cites this paper
Truthful online spectrum allocation and auction in multi-channel wireless networks
2011cites this paper
Offline file assignments for online load balancing
2011cites this paper
Improved bounds for online scheduling with eligibility constraints
2011cites this paper
Generalized Online Malleable Job Scheduling on Three Processors
2011cites this paper
Online scheduling with rearrangement on two related machines
2011cites this paper
New upper and lower bounds for online scheduling with machine cost
2010cites this paper
A Robust PTAS for Machine Covering and Packing
2010cites this paper
SALSA: Strategyproof Online Spectrum Admissions for Wireless Networks
2010cites this paper
Online parallel machines scheduling with two hierarchies
2009cites this paper
Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead
2009cites this paper
Online Scheduling & Project Scheduling
2009cites this paper
SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks
2009cites this paper
Online market driven spectrum scheduling and auction
2009cites this paper
Online Bicriteria Load Balancing Using Object Reallocation
2009cites this paper
The Power of Reordering for Online Minimum Makespan Scheduling
2008influential citation
Online Balancing Two Independent Criteria
2008cites this paper
Online scheduling with reassignment
2008cites this paper
Online scheduling for buffering problems
2008cites this paper
Seventh Cologne Twente Workshop on Graphs and Combinatorial Optimization, gargano, Italy, 13-15 May, 2008
2008cites this paper
List’s worst-average-case or WAC ratio
2008cites this paper
Online Algorithms for Scheduling with Machine Activation Cost
2007cites this paper