Three-partitioning containing kernels: Complexity and heuristic

DOI10.1007/BF02247409MaRDI QIDQ1924322zbMATH OpenOpenAlexFDO

Authors Yong He, Enyu Yao, Shiping Chen

Publication date 23 February 1997

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02247409

zbMATH Keywords

heuristicNP-completeworst case boundLPT-algorithm\(k\)-partitioning containing kernels

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A tight bound for 3-partitioning
• scientific article; zbMATH DE number 1112368
• The \(k\)-partitioning problem
• A 3/2-approximation algorithm for k_i-partitioning
• 3-partitioning problems for maximizing the minimum load

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A tight bound for 3-partitioning
• Bounds on Multiprocessing Timing Anomalies
• Constrained partitioning problems
• Optimal Set Partitioning
• Optimal partitions
• Parallel machines scheduling with nonsimultaneous machine available time

Cited in

(4)

• scientific article; zbMATH DE number 800169 (Why is no real title available?)
• A tight bound for 3-partitioning
• The multifit algorithm for set partitioning containing kernels
• Three Partition Refinement Algorithms

This page was built for publication: Three-partitioning containing kernels: Complexity and heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924322)