In this paper the utility and the difficulties of probabilisticanalysis for optimization algorithms are discussed. Such an analysis is expected to deliver valuable criteria-better than the worst-case complexity-for t...
详细信息
In this paper the utility and the difficulties of probabilisticanalysis for optimization algorithms are discussed. Such an analysis is expected to deliver valuable criteria-better than the worst-case complexity-for the efficiency of an algorithm in practice.
In the k-dimensional packing problem, we are given a set I=(b(1), b(2),..., b(n)) of k-dimensional boxes and a k-dimensional box B with unit length in each of the first k-1 dimensions and unbounded length in the kth d...
详细信息
In the k-dimensional packing problem, we are given a set I=(b(1), b(2),..., b(n)) of k-dimensional boxes and a k-dimensional box B with unit length in each of the first k-1 dimensions and unbounded length in the kth dimension. Each box b(i) is represented by a k-tuple b(i) = (x(i)((1)),..., x(i)((k-1)), x(i)((k))) is an element of (0, 1](k-1) X (0, infinity), where x((j)) denotes its length in the jth dimension, 1 less than or equal to j less than or equal to k. We are asked to find a packing of I into B such that each box is packed orthogonally and oriented in all k dimensions and such that the height in the kth dimension of the packing is minimized. The k-dimensional packing problem is known to be NP-hard for each k > 1. In this note, we study the average-case behavior of a class of algorithms, which includes any optimal algorithm and an on-line algorithm. Let A denote an algorithm in this class. Assume that b(1), b(2),..., b(n) are independent, identically distributed according to a distribution F(x((1)),.., x((k-1)), x((k))) over (0, 1](k-1) X (0, infinity), and the marginal distribution F-k of x((k)) satisfies the property that there is a positive number Lu at which the moment generating function M(Fk)(t) has a finite value C-a > 0. It is shown that for each given s > 0, there is an N-s,N-F > 0 such that for all n greater than or equal to N-s,N-F, Pr(\A(b(1),..., b(n))/n - Gamma\>s) < (2 + C-a)exp(-(sa/3)(2/3)n(1/3)), where Gamma = lim(n-->infinity)E[A(b(1),..., b(n))]/n and A(b(1),..., b(n)) denotes the height in the kth dimension of the packing of (b(1),..., b(n)) produced by A.
This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions...
详细信息
This paper is concerned with the design and probabilistic analysis of algorithms for the maximum-flow problem and capacitated transportation problems. These algorithms run in linear time and, under certain assumptions about the probability distribution of edge capacities, obtain an optimal solution with high probability. The design of our algorithms is based on the following general method, which we call the mimicking method, for solving problems in which some of the input data are deterministic and some are random with a known distribution: 1. Replace each random variable in the problem by its expectation;this gives a deterministic problem instance that has a special form, making it particularly easy to solve;2. Solve the resulting deterministic problem instance;3. Taking into account the actual values of the random variables, mimic the solution of the deterministic instance to obtain a near-optimal solution to the original problem;4. Fine-tune this suboptimal solution to obtain an optimal solution. We present linear time algorithms to compute a feasible flow in directed and undirected capacitated transportation problem instances. The algorithms are shown to be successful with high probability when the probability distribution of the input data satisfies certain assumptions. We also consider the maximum flow problem with multiple sources and sinks. We show that with high probability the minimum cut isolates either the sources or the sinks, and we give a linear-time algorithm that produces a maximum flow with high probability.
We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n numbers drawn from {0,1,2,..., m-1} with repetiti...
详细信息
We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n numbers drawn from {0,1,2,..., m-1} with repetitions allowed;we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilisticanalysis of a grouping algorithm called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m-->infinity or as n/m-->0.
In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n x m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}...
详细信息
In this paper, we provide bounds for the expected value of the log of the condition number C(A) of a linear feasibility problem given by a n x m matrix A (Ref. 1). We show that this expected value is O(min{n, m log n}) if n > m and is \cat O(log n) otherwise. A similar bound applies for the log of the condition number C-R(A) introduced by Renegar (Ref. 2).
This paper proposes a new sequential probabilistic back analysis approach for probabilistically determining the uncertain geomechanical parameters of shield tunnels by using time-series monitoring data. The approach i...
详细信息
This paper proposes a new sequential probabilistic back analysis approach for probabilistically determining the uncertain geomechanical parameters of shield tunnels by using time-series monitoring data. The approach is proposed based on the recently developed Bayesian updating with subset simulation. Within the framework of the proposed approach, a complex Bayesian back analysis problem is transformed into an equivalent structural reliability problem based on subset simulation. Hermite polynomial chaos expansion-based surrogate models are constructed to improve the computational efficiency of probabilistic back analysis. The reliability of tunneling-induced ground settlements is updated in the process of sequential back analyses. A real shield tunnel project of No. 1 Nanchang Metro Line in China is investigated to assess the effectiveness of the approach. The proposed approach is able to infer the posterior distributions of uncertain geomechanical parameters (i.e., Young's moduli of surrounding soil layers and ground vehicle load). The reliability of tunneling-induced ground settlements can be updated in a real-time manner by fully utilizing the time-series monitoring data. The results show good agreement with the variation trend of field monitoring data of ground settlement and the post-event investigations.
We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost fo...
详细信息
We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost for the metric vehicle routeing problem and analyze them in this setting. We prove that there exists a constant (c) over cap > 0 such that the iterated tour partitioning heuristic given by Haimovich and Rinnooy Kan (1985) is a (2 - (c) over cap)-approximation algorithm with probability arbitrarily close to I as the number of customers goes to infinity. It has been a longstanding open problem as to whether one can improve upon the factor of 2 given by Haimovich and Rinnooy Kan. We also generalize this, and previous results, to the multidepot case.
A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in the k-dimensional Euclidean space E(k), k > 1, projects the given point set S onto the x-axis. For each point q is-an-element...
详细信息
A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in the k-dimensional Euclidean space E(k), k > 1, projects the given point set S onto the x-axis. For each point q is-an-element-of S a nearest neighbor in S under any L(p)-metric (1 less-than-or-equal-to p less-than-or-equal-to infinity) is found by sweeping from q into two opposite directions along the x-axis. If delta(q) denotes the distance between q and its nearest neighbor in S the sweep process stops after all points in a vertical 2-delta(q)-slice centered around q have been examined. We show that this algorithm solves the all-nearest-neighbors problem for n independent and uniformly distributed points in the unit cube [0, 1]k in THETA(n2 -1/k) expected time, while its worst-case performance is THETA(n2).
We consider the problem of choosing K “medians” among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-...
详细信息
We consider the problem of choosing K “medians” among n points on the Euclidean plane such that the sum of the distances from each of the n points to its closest median is minimized. We show that this problem is NP-complete. We also present two heuristics that produce arbitrarily good solutions with probability going to 1. One is a partition heuristic, and works when K grows linearly—or almost so—with n. The other is the “honeycomb” heuristic, and is applicable to rates of growth of K of the form K∼n
location problem
K-median problem
NP-complete problem
probabilistic analysis of algorithms
暂无评论