\(\kappa\)-partitioning problems for maximizing the minimum load

DOI10.1016/S0898-1221(03)90201-XzbMath1116.90390OpenAlexW1965788090MaRDI QIDQ1879573

Yong He, Zhiyi Tan, Jing Zhu, Enyu Yao

Publication date: 23 September 2004

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0898-1221(03)90201-x

zbMATH Keywords

SchedulingPartitioningAnalysis of algorithmWorst case ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (7)

EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ EPTAS for parallel identical machine scheduling with time restrictions ⋮ Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint ⋮ Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint ⋮ Optimal matroid partitioning problems ⋮ \(k\)-partitioning problems with partition matroid constraint ⋮ Unnamed Item

Cites Work

• 3-partitioning problems for maximizing the minimum load
• The exact LPT-bound for maximizing the minimum completion time
• Semi on-line algorithms for the partition problem
• The \(k\)-partitioning problem
• A tight bound for 3-partitioning
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times
• Ordinal algorithms for packing with target center of gravity
• Ordinal algorithms for parallel machine scheduling
• Bin packing using semi-ordinal data
• The Multiple Subset Sum Problem
• On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies
• Scheduling workers in a constricted area
• A 7/6–Approximation Algorithm For 3-Partitioning And Its Application To Multiprocessor Scheduling
• Bounds for the cardinality constrained \(P \|C_{max}\) problem
• Semi-on-line scheduling with ordinal data on two uniform machines

This page was built for publication: \(\kappa\)-partitioning problems for maximizing the minimum load