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

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