English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A simple algorithm for solving the knapsack problem is shown to lead to examining, on the average, around e2 vectors out of 2". Most optimization methods can be considered as devices for reducing the number of possible solutions that need to be examined and compared. The efficiency of an algorithm is determined to a large extent by what fraction of the total number of possible solutions has to be examined in the process of application of the algorithm. Computational experience shows that this fraction is usually very small for many inputs, but not for all: even the simplex method is shown to be inefficient in the worst case [1]. Accordingly, such algorithms are relatively fast for many inputs, but do not have good uniform computing time bounds. Moreover, most operations research problems are known to be NP-hard [2] and one can expect any algorithm for any NP-hard problem to be intractable in the sense of worst case performance. For this reason, it is of interest to obtain the average values of parameters determining the computing time. In this paper we compute the expected number of vectors examined in the course of application of a simple algorithm for the knapsack problem (zero-one programming problem with a single constraint). The algorithm is quite primitive as compared to the methods actually used in computational practice. However, the idea employed in this algorithm to reduce the number of possible solutions is similar to the ideas on which "real" integer programming algorithms are based. It is hoped, therefore, that the result below may give a rough idea of the computational efficiency of "real" methods. The average computing time of such methods is very hard to find, and one often relies on empirical testing. Horowitz and Sahni [3] compare the results of an empirical study of a few knapsack algorithms. Knuth [4] discusses a general Monte-Carlo method for estimating the average efficiency of backtracking algorithms. During this work I have benefited from conversations with many mathematicians, and I should especially mention I. Davidova, N. Maslova, B. Pittel, I. Romanovsky and the late Yu. Burtin. Received by the editors June 5, 1979. AMS (MOS) subject classifications (1970). Primary 68A20, 90C10.

The efficiency of an algorithm of integer programming: a probabilistic analysis