SOME VERY EASY KNAPSACK/PARTITION PROBLEMS

J. B. Orlin

No 272288, Econometric Institute Archives from Erasmus University Rotterdam

Abstract: Consider the problem of partitioning a group of b indistinguishable objects into subgroups each of size at least X and at most u. The objective is to minimize the additive separable cost of the partition, where the cost associated with a subgroup of size j is c(j). In the case that c(.) is convex, we show how to solve the problem in O(log u) steps. In the case that c(.) is concave, we solve the problem in 0(min(X, b/u, (b/k)—(b/u), u—X)) steps. This problem generalizes a lot—sizing result of Chand and has potential applications in clustering.

Keywords: Agricultural and Food Policy; Research Methods/Statistical Methods (search for similar items in EconPapers)
Pages: 14
Date: 1984
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ageconsearch.umn.edu/record/272288/files/erasmus164.pdf (application/pdf)
https://ageconsearch.umn.edu/record/272288/files/erasmus164.pdf?subformat=pdfa (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:eureia:272288

DOI: 10.22004/ag.econ.272288

Access Statistics for this paper

More papers in Econometric Institute Archives from Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().