Worst case analysis of two heuristics for the set partitioning problem

DOI10.1051/ITA/1987210100111MaRDI QIDQ3774940zbMATH OpenOpenAlexFDO

Authors A. Marchetti Spaccamela, Antonella Pelaggi

Publication date 1987

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92274

zbMATH Keywords

schedulingset partitioning problem

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Worst-case analysis of the differencing method for the partition problem
• A set partitioning heuristic for the generalized assignment problem
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• A new worst-case bound of heuristic for set covering problem
• Worst-case analysis of an approximation scheme for the subset-sum problem
• Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics
• scientific article; zbMATH DE number 850316
• Heuristics, cutting planes and subgradient optimization for set partitioning problems
• Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
• Worst-case analysis of the set-union problem with extended backtracking

Cites work

• Approximation algorithms for combinatorial problems
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3604658 (Why is no real title available?)
• Worst-case analysis of the differencing method for the partition problem

Cited in

(5)

• Magic sets revisited
• On domain-partitioning induction criteria: worst-case bounds for the worst-case based
• Worst-case analysis of the differencing method for the partition problem
• scientific article; zbMATH DE number 1031387 (Why is no real title available?)
• A new worst-case bound of heuristic for set covering problem

This page was built for publication: Worst case analysis of two heuristics for the set partitioning problem

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