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

DOI10.1007/BF02591687zbMath0609.90094OpenAlexW2016357237MaRDI QIDQ3750527

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 algorithmspartition problemworst-case performance ratioKarmarkar-Karp differencing method

Mathematics Subject Classification ID

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

Related Items (6)

Performance ratios of the Karmarkar-Karp differencing method ⋮ 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 ⋮ Unnamed Item ⋮ Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems

Cites Work

• Unnamed Item

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