The bounded subset sum problem is almost everywhere randomly decidable in O(n) (Q1083370)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The bounded subset sum problem is almost everywhere randomly decidable in O(n)
scientific article

    Statements

    The bounded subset sum problem is almost everywhere randomly decidable in O(n) (English)
    0 references
    0 references
    0 references
    1986
    0 references
    The subset sum problem is to decide, whether for given positive integers b, \(a_ i\), \(1\leq i\leq n\) the equation \[ (SS)\quad b=\max \{\sum a_ ix_ i| \sum a_ ix_ i\leq b,\quad x_ i\in \{0,1\},\quad 1\leq i\leq n\} \] is true. Given a sequence \(A=(A_ n)_{n\in N}\) of positive integers with \(A_ n=o(n)\) the A-bounded subset sum problem SS(A) is the set of all problem instances of type (SS) with \(a_ i\in \{1,...,A_ n\}\) and \(b\in \{1,...,nA_ n\}\). We show that for each A-bounded subset sum problem SS(A) an 0(n) randomized greedy algorithm finds the correct maximum with probability 1/2 for almost all problem instances. Hence the A-bounded subset sum problem is almost everywhere randomly decidable in 0(n).
    0 references
    subset sum problem
    0 references
    A-bounded subset sum problem
    0 references
    randomized greedy algorithm
    0 references

    Identifiers