Worst-case analysis of the differencing method for the partition problem

DOI10.1007/BF02591687MaRDI QIDQ3750527zbMATH OpenOpenAlexFDO

Authors Matteo Fischetti, Silvano Martello

Publication date 1987

Published in Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

heuristic algorithmsKarmarkar-Karp differencing methodpartition problemworst-case performance ratio

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Worst case analysis of two heuristics for the set partitioning problem
• A note on the average-case behavior of a simple differencing method for partitioning
• Analysis of algorithms for a class of continuous partition problems
• scientific article; zbMATH DE number 1538871
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• scientific article; zbMATH DE number 1962846
• Worst-case analysis of an approximation scheme for the subset-sum problem
• scientific article; zbMATH DE number 1161371
• scientific article; zbMATH DE number 850316
• scientific article; zbMATH DE number 1472145

Cited in

(7)

• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• On domain-partitioning induction criteria: worst-case bounds for the worst-case based
• The longest processing time rule for identical parallel machines revisited
• Worst case analysis of two heuristics for the set partitioning problem
• Computer-assisted proof of performance ratios for the differencing method
• scientific article; zbMATH DE number 2230249 (Why is no real title available?)
• Performance ratios of the Karmarkar-Karp differencing method

This page was built for publication: Worst-case analysis of the differencing method for the partition problem

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