Sums of lexicographically ordered sets
type: Item
instance of: scholarly article
title: Sums of lexicographically ordered sets
zbMATH Open document ID: 0698.90059
DOI: 10.1016/0012-365X(90)90112-U
author: Alberto Negro
author: N. Santoro
author: Michael D. Atkinson
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: Given a set \(A=\{a_ 1,..,a_ n\}\) of distinct positive integers where \(a_ i<a_{i+1}\), \(i=1,...,n-1\). The knapsack problem on A is the problem of determining for any integer b whether b can be expressed as a sum of distinct elements and, if so, of identifying such elements. The authors consider the problem of determining sets A which are knapsack- solvable in linear time (for any integer b) and where the largest element is as small as possible. This is done by studying the condition that the k-subsets (for fixed k) of A when lexicographically ordered have increasing sums, and by constructing such sets.
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 05A99
zbMATH DE Number: 4145662
zbMATH Keywords: linear solvability
zbMATH Keywords: knapsack problem
reviewed by: Joachim Piehler
MaRDI profile type: Publication
cites work: Sets of Integers Whose Subsets Have Distinct Sums
cites work: Unsolved problems in number theory
cites work: Integer Sets with Distinct Subset-Sums
cites work: Hiding information and signatures in trapdoor knapsacks
description: scientific article; zbMATH DE number 4145662