Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

DOI10.1137/0204021zbMath0315.68040OpenAlexW1999370138MaRDI QIDQ4076768

No author found.

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204021

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Information storage and retrieval of data (68P20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

A note on minimizing the sum of squares of machine completion times on two identical parallel machines ⋮ An asymptotically exact polynomial algorithm for equipartition problems ⋮ Partitioning ideal sets ⋮ Tighter bounds on a heuristic for a partition problem ⋮ A dual criteria sequencing problem with earliness and tardiness penalties ⋮ A fast and effective subset sum based improvement procedure for workload balancing on identical parallel machines ⋮ Using \(\ell^p\)-norms for fairness in combinatorial optimisation ⋮ Weighted flow time bounds for scheduling identical processors ⋮ Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements ⋮ Optimal partitions ⋮ The benefit of preemption with respect to the \(\ell_p\) norm ⋮ A Lower Bound for the On-Line Preemptive Machine Scheduling with ℓ p Norm ⋮ Tight bounds for selfish and greedy load balancing ⋮ Tight Bounds for Online Vector Scheduling ⋮ An efficient polynomial time approximation scheme for load balancing on uniformly related machines ⋮ Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing ⋮ Analysis of set-up time models: a metric perspective ⋮ Frameworks for adaptable scheduling algorithms ⋮ An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines ⋮ A new model for selfish routing ⋮ Quality of move-optimal schedules for minimizing total weighted completion time ⋮ Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data ⋮ A two-phase heuristic for strip packing: Algorithm and probabilistic analysis ⋮ Load balancing of temporary tasks in the \(\ell _{p}\) norm ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ Resource constrained scheduling as generalized bin packing ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ Partitioning under the \(L_p\) norm ⋮ Approximation scheduling algorithms: a survey ⋮ Task allocation in fault-tolerant distributed systems ⋮ Price-based protocols for fair resource allocation ⋮ A tight upper bound for the \(k\)-partition problem on ideal sets ⋮ On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines ⋮ Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function ⋮ Extending Graham's result on scheduling to other heuristics ⋮ Approximation algorithms for shop scheduling problems with minsum objective ⋮ Parallel machine earliness and tardiness scheduling with proportional weights ⋮ An analysis of the LPT algorithm for the max-min and the min-ratio partition problems

This page was built for publication: Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation