A note on the complexity of a partition algorithm
type: Item
instance of: scholarly article
title: A note on the complexity of a partition algorithm
zbMATH Open document ID: 0531.68022
DOI: 10.1016/0020-0190(83)90049-2
author: Vladimir Lifschitz
author: Leon Pesotchinsky
published in: Information Processing Letters
publication date: 1983-01-01T00:00:00Z
review text: In this paper we present the results of the theoretical analysis of a simplified version of the partition procedure PARTS described by \textit{E. Horowitz} and \textit{S. Sahni} [J. Assoc. Comput. Mach. 21, 277-292 (1974; Zbl 0329.90046)]. Its worst-case behavior is shown to be strictly exponential. On the other hand, for \(x_ 1,...,x_ n\) chosen at random in an initial segment of positive integers, we show that, with a probability close to 1, the computation time of PARTS grows as ex\(p\{\) \(c\sqrt{n}\}\).
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3843150
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: partition problem
MaRDI profile type: Publication
full work available at URL: 0020-0190(83)90049-2
OpenAlex ID: W2084120288
cites work: Q5560061
cites work: Determining the Stability Number of a Graph
cites work: Hard Knapsack Problems
cites work: Q4198056
cites work: Computing Partitions with Applications to the Knapsack Problem
cites work: A Tauberian theorem for partitions
cites work: The Efficiency of an Algorithm of Integer Programming: A Probabilistic Analysis
cites work: The Worst and the Most Probable Performance of a Class of Set-Covering Algorithms
cites work: Determining the Chromatic Number of a Graph
description: scientific article; zbMATH DE number 3843150