Worst-case analysis of greedy algorithms for the subset-sum problem

Given a set ofn positive integers and another positive integerW, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding,W. We present a polynomial approximation scheme for this problem and prove that its worst-case performance dominates that of Johnson's well-known scheme. Research supported by Ministero Pubblica Istruzion, Italy.     

Worst-case analysis of an approximation scheme for the subset-sum problem

Given a set of n integers, the Subset-Sum Problem is to find that subset whose sum is closent to, without exceeding, a given integer W. In this paper we analyse Martello and Toth's polynomial approximation scheme for the problem, showing that its worst-case performance is better than the lower bound they proved, although not so good as conjectured.     

Approximation schemes for the subset-sum problem: Survey and experimental analysis

Given a set of n positive integers w₁,…,w_n and a positive integer W, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, W. The most important heuristics for this problem are approximation schemes based on a worst-case analysis. We survey them and experimentally analyze their statistical behaviour on a large number of test problems.     

Probabilistic analysis of the generalised assignment problem

We analyse thegeneralised assignment problem under the assumption that all coefficients are drawn uniformly and independently from [0, 1]. We show that such problems can be solved exactly with high probability, in a well-defined sense. The results are closely related to earlier work of Lueker, Goldberg and Marchetti-Spaccamela and ourselves.Supported by NATO grant RG0088/89.Supported by NSF grant CCR-8900112 and NATO grant RG0088/89.     

Probabilistic analysis of solving the assignment problem for the traveling salesman problem

This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time $\text{O}\text{(}\text{n}{}^4\text{3}\text{)}$, and (iii) it requires less than w((w + n ? 1)$\text{log}\text{(w + n ? 1) + w + 1) +}\text{1}\text{6}\text{w(n}{}^3\text{+ 3n}{}^2\text{+ 2n ? 6)}$ computational steps, where w = log(s)/log(1 ? E_n); E_n ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem.     

Probabilistic analysis of the pure literal heuristic for the satisfiability problem

An algorithm for the SATISFIABILITY problem is presented and a probabilistic analysis is performed. The analysis is based on an instance distribution which is parametrized to simulate a variety of sample characteristics. The algorithm either correctly determines whether a given instance of SATISFIABILITY has a solution or gives up. It is shown that the algorithm runs in polynomial time and gives up with probability approaching zero as input size approaches infinity for a range of parameter values. This result is an improvement over the results in [3] and [4].     

Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

We look at the instance distributions used by Goldberg [3] for showing that the Davis Putnam Procedure has polynomial average complexity and show that, in a sense, all these distributions are unreasonable. We then present a ‘reasonable’ family of instance distributions F and show that for each distribution in F a variant of the Davis Putnam Procedure without the pure literal rule requires exponential time with probability 1. In addition, we show that adding subsumption still results in exponential complexity with probability 1.     

Probabilistic approach to the neumann problem

The basic problem considered in this paper is to solve the following Neumann boundary value problem probabilistically: where we assume that q is in a certain functional class to be specified below, and φ is a bounded measurable function on the boundary. We give a martingale formulation of the Neumann problem and show that this formulation is essentially equivalent to the classical formulation. The paper culminates in an explicit formula for the solution of this problem in terms of reflecting Brownian motion and its boundary local time.     

Probabilistic approach to the Neumann problem

In this paper, we consider the Neumann boundary value problem of Schrödinger operator with measure potential . First, a martingale formulation of the Neumann problem and an analytic characterization of the martingale formulation are given. Then, by using the Dirichlet forms and Stochastic analysis we obtain an explicit formula for the unique weak solution of this problem in terms of reflecting Brownias motion and it's boundary local time.     

Probabilistic time-dependent vehicle routing problem

Central European Journal of Operations Research - The probabilistic time-dependent vehicle routing problem is presented in this paper. It is a novel variant of the vehicle routing problem. The...     

Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection

A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE ^k ,k>1, projects the given point setS onto thex-axis. For each pointq S a nearest neighbor inS under anyL _p -metric (1 p ) is found by sweeping fromq into two opposite directions along thex-axis. If _q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2 _q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] ^k in (n ^2–1/k ) expected time, while its worst-case performance is (n ²).     

Probabilistic analysis of an approximation algorithm for the traveling salesman problem on unbounded above instances

The probabilistic analysis of a modification of the approximation algorithm “Nearest City” is presented for the traveling salesman minimization problem. The case is considered when the entries of the distance matrix are some independent identically distributed random variables with the values in the range [a _n ,∞), a _n > 0, that are unbounded above and have a truncated normal or exponential distribution. We obtain the estimates of relative errors, the failure probabilities, and also the conditions of asymptotic optimality of the algorithm. The modification of the algorithm allows us to perform analysis so that the obtained results are true for the traveling salesman problems in the cases of both directed and undirected graphs.     

Probabilistic analysis of an algorithm for the m-planar 3-index assignment problem on single-cycle permutations

Under study is them-planar 3-index assignment problem on single-cycle permutations, which is, in other words, the m peripatetic salesman problem (m-PSP) with different weight functions for each salesman. The problem is NP-hard for m ≥ 1. Some polynomial approximation algorithm is suggested for 1 <m < n/4 with time complexity O(nm ²). The performance ratios of the algorithm are established for the input data (elements of m× n × n matrix) which are assumed to be independent and identically distributed random variables on [a _n , b _n ], where 0 < a _n < b _n . If the distribution function is uniform or dominates (majorizes) the uniform distribution then some conditions on a _n , b _n , and m are obtained for the algorithm to be the asymptotically exact.     

Probabilistic bounds and algorithms for the maximum satisfiability problem

In this paper we present a new method to analyze and solve the maximum satisfiability problem. We randomize the Boolean variables, assign probabilities to their possible values and, by using recently developed probabilistic bounds of the authors, present a deterministic procedure to obtain solution to the maximum satisfiability problem. Our algorithm generalizes the heuristic procedure given by Johnson, 1974.Research supported by AFOSR Grants 0271, 0066 and by NSF Grant 85-03212.     

Probabilistic approach to the Neumann problem with infinite gauge

We provide in this paper a probabilistic approach to the Neumann problem of Schrödinger equations without the assumption of the finiteness of the gauge, i.e., without the assumption that the underlying Schrödinger operator admits only negative eigenvalues. This approach unifies and generalizes both the results of Hsu Pei and of G. A. Brosamlar.     

Probabilistic approach to the Dirichlet problem of second order elliptic PDE

In this paper we provide a probabilistic approach to the following Dirichlet Problem{(∑x~4(α~(ij) x~j) ∑b~ix~i ξ)u=0, iD u=g, on D,without assuming that the eigenvalues of the operator∑x~i(α~(ij)x~j) ∑b~ix~i ξwith Dirichlet boundary conditions are all strictly negative. The results of this paper generalizedthose of Ma.