The randomized algorithm for finding an eigenvector of the stochastic matrix with application to PageRank

The problem of finding the eigenvector corresponding to the largest eigenvalue of a stochastic matrix has numerous applications in ranking search results, multi-agent, consensus, networked control and data mining. The power method is a typical tool for its solution. However randomized methods could be competitors vs standard ones; they require much less calculations for one iteration and are well tailored for distributed computations. We propose a new randomized algorithm and provide upper bound for its rate of convergence which is O(lnN/n), where N is the dimension and n is the number of iterations. The bound looks promising because lnN is not large even for very high dimensions. The algorithm is based on the mirror-descent method for convex stochastic optimization. Applications to PageRank problem are discussed. Published in Russian in Doklady Akademii Nauk, 2009, Vol. 426, No. 6, pp. 734–737. Presented by Academician S.N. Vasil’ev February 9, 2009 The article was translated by the authors.     

Algorithms for a stochastic selective travelling salesperson problem

In this paper, the selective travelling salesperson problem with stochastic service times, travel times, and travel costs (SSTSP) is addressed. In the SSTSP, service times, travel times and travel costs are known a priori only probabilistically. A non-negative value of reward for providing service is associated with each customer and there is a pre-specified limit on the duration of the solution tour. It is assumed that not all potential customers can be visited within this tour duration limit, even under the best circumstances. And, thus, a subset of customers must be selected. The objective of the SSTSP is to design an a priori tour that visits each chosen customer once such that the total profit (total reward collected by servicing customers minus travel costs) is maximized and the probability that the total actual tour duration exceeds a given threshold is no larger than a chosen probability value. We formulate the SSTSP as a chance-constrained stochastic program and propose both exact and heuristic approaches for solving it. Computational experiments indicate that the exact algorithm is able to solve small- and moderate-size problems to optimality and the heuristic can provide near-optimal solutions in significantly reduced computing time.     

Stochastic games with non-observable actions

We examine n-player stochastic games. These are dynamic games where a play evolves in stages along a finite set of states; at each stage players independently have to choose actions in the present state and these choices determine a stage payoff to each player as well as a transition to a new state where actions have to be chosen at the next stage. For each player the infinite sequence of his stage payoffs is evaluated by taking the limiting average. Normally stochastic games are examined under the condition of full monitoring, i.e. at any stage each player observes the present state and the actions chosen by all players. This paper is a first attempt towards understanding under what circumstances equilibria could exist in n-player stochastic games without full monitoring. We demonstrate the non-existence of -equilibria in n-player stochastic games, with respect to the average reward, when at each stage each player is able to observe the present state, his own action, his own payoff, and the payoffs of the other players, but is unable to observe the actions of them. For this purpose, we present and examine a counterexample with 3 players. If we further drop the assumption that the players can observe the payoffs of the others, then counterexamples already exist in games with only 2 players.     

Embedding a novel objective function in a two-phased local search for robust vertex coloring

In this paper, we propose a two-phased local search for vertex coloring. The algorithm alternately executes two closely interacting functionalities, i.e., a stochastic and a deterministic local search. The stochastic phase is basically based on biased random sampling that, according to a probability matrix storing the probability a vertex can be assigned to a color, iteratively constructs feasible colorings. The deterministic phase, instead, consists in assigning sequentially, according to a given ordering, each vertex to the color which causes the lowest increase of the solution penalty, and then, when the schedule is constructed, swap operations are executed to improve the performance. The interaction between the two phases is implemented by tunnelling information of what happened during a phase to the successive ones. Beyond the algorithm scheme, the novelty of the approach stems from the fact that the objective function is not minimizing the number of colors but a new penalty function. The proposed approach is tested on known benchmarks for the studied problem available on the public domain. From a comparison to the state of the art it appears that the proposed approach is robust and is able to achieve best known results.     

On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Random walk search procedures for reliability optimization of systems with fault tolerance

In this paper we develop two efficient discrete stochastic search methods based on random walk procedure for maximizing system reliability subjected to imperfect fault coverage where uncovered component failures cause immediate system failure, even in the presence of adequate redundancy. The first search method uses a sequential sampling procedure with fixed boundaries at each iteration. We show that this search process satisfies local balance equations and its equilibrium distribution gives most weight to the optimal solution. We also show that the solution that has been visited most often in the first m iterations converges almost surely to the optimal solution. The second search method uses a sequential sampling procedure with increasing boundaries at each iteration. We show that if the increase occurs slower than a certain rate, this search process will converge to the optimal set with probability 1. We consider the system where reliability cannot be evaluated exactly but must be estimated through Monte Carlo simulation. Copyright © 2008 John Wiley & Sons, Ltd.     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

A comparison of feasible direction methods for the stochastic transportation problem

The feasible direction method of Frank and Wolfe has been claimed to be efficient for solving the stochastic transportation problem. While this is true for very moderate accuracy requirements, substantially more efficient algorithms are otherwise diagonalized Newton and conjugate Frank–Wolfe algorithms, which we describe and evaluate. Like the Frank–Wolfe algorithm, these two algorithms take advantage of the structure of the stochastic transportation problem. We also introduce a Frank–Wolfe type algorithm with multi-dimensional search; this search procedure exploits the Cartesian product structure of the problem. Numerical results for two classic test problem sets are given. The three new methods that are considered are shown to be superior to the Frank–Wolfe method, and also to an earlier suggested heuristic acceleration of the Frank–Wolfe method.     

A tabu search tutorial based on a real-world scheduling problem

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n ³) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).     

Fast Nonparametric Density-Based Clustering of Large Datasets Using a Stochastic Approximation Mean-Shift Algorithm

Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n²) per iteration, it does not scale well to large datasets. We propose a novel algorithm which performs density-based clustering much quicker than mean shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. Its performances are evaluated using simulations and applications to image segmentation, where the algorithm was tens or hundreds of times faster than mean shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with existing approaches to further accelerate clustering.     

Improvement on the northby algorithm for molecular conformation: Better solutions

In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states ofn-atom Lennard-Jones clusters and reported putative global minima for 13n150. In this paper, we introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search fromO(n^5/3) per move toO(n^2/3) per move for ann-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced toO(logn) per move for ann-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxingevery lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm forn=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.     

Off-Line Maintenance of Planar Configurations

We achieve anO(log n) amortized time bound per operation for the off-line version of the dynamic convex hull problem in the plane. In this problem, a sequence ofninsert,delete, andqueryinstructions are to be processed, where each insert instruction adds a new point to the set, each delete instruction removes an existing point, and each query requests a standard convex hull search. We process the entire sequence in totalO(n log n) time andO(n) space. Alternatively, we can preprocess a sequence ofninsertions and deletions inO(n log n) time and space, then answer queries in history inO(log n) time apiece (a query in history means a query comes with a time parametert, and it must be answered with respect to the convex hull present at timet). The same bounds also hold for the off-line maintenance of several related structures, such as the maximal vectors, the intersection of half-planes, and the kernel of a polygon. Achieving anO(log n) per-operation time bound for theon-lineversions of these problems is a longstanding open problem in computational geometry.     

在线时间序列搜索的风险补偿模型

对于在线时间序列搜索问题,在假设对未来信息有一定的预期下,提出了在线时间序列搜索的风险补偿模型,进一步研究了模型的求解,给出了模型的一个最优策略,并通过数值计算讨论了最优策略的补偿函数随参数变化规律.数值实验结果表明,随着风险容忍度的增大与预期区间下限的增大,补偿函数均增大且趋于收敛;随着预期概率的增大与预期区间上限的减少,补偿函数分别增大.研究结果丰富了在线时间序列搜索的理论且具有实际应用价值.     

Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem

In this paper we propose a weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, we only use full-Newton step. Finally, the currently best known iteration bound for the algorithm with a small-update method, namely, O(√nlog n/ε) is derived, which is as good as the bound for the linear optimization analogue.     

The Las-Vegas Processor Identity Problem (How and When to Be Unique)

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is that upon termination of the algorithm, the processes must have unique IDs always. Our results include tight characterization of the problem in several respects. We call a protocol solving this task Las Vegas if it has finite expected termination time. Our main positive result is the first Las-Vegas protocol that solves the problem. The protocol terminates in O(log n) expected asychronous rounds, using O(n) shared memory space, where n is the number of participating processes. The new protocol improves on all previous solutions simultaneously in running time (exponentially), probability of termination (to 1), and space requirement. The protocol works under the assumption that the asynchronous schedule is oblivious, i.e., independent of the actual unfolding execution. On the negative side, we show that there is no finite-state Las-Vegas protocol for the problem if the schedule may depend on the history of the shared memory (an adaptive schedule). We also show that any Las-Vegas protocol must know n in advance (which implies that crash faults cannot be tolerated) and that the running time is Ω(log n). For the case of an arbitrary (nonoblivious) adversarial schedule, we present a Las-Vegas protocol that uses O(n) unbounded registers. For the read-modify-write model, we present a constant-space deterministic algorithm.     

David G. Luenberger,Linear and nonlinear programming, 2nd edition,Addison-Wesley,Reading (1984), xv + 492 pages, $35.50

This paper considers a stochastic version of the linear continuous type knapsack problem in which the cost coefficients are random variables. The problem is to find an optimal solution and an optimal probability level of the chance constraint. This problem P₀ is first transformed into a deterministic equivalent problem P. Then a subproblem with a positive parameter is introduced and a close relation between P and its subproblem is shown. Further, an auxiliary problem of the subproblem is introduced and a direct relation between P and the auxiliary problem is derived through a relation connecting the subproblem and its auxiliary problem. Fully utilizing these relations, an efficient algorithm is proposed that finds an optimal solution of P in at most O(n⁴) computational time where n is the number of decision variables. Finally, further research problems are discussed.     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor

We present real, complex, and quaternionic versions of a simple randomized polynomial time algorithm to approximate the permanent of a nonnegative matrix and, more generally, the mixed discriminant of positive semidefinite matrices. The algorithm provides an unbiased estimator, which, with high probability, approximates the true value within a factor of O(cⁿ), where n is the size of the matrix (matrices) and where c ≈ 0.28 for the real version, c ≈ 0.56 for the complex version, and c ≈ 0.76 for the quaternionic version. We discuss possible extensions of our method as well as applications of mixed discriminants to problems of combinatorial counting. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 29–61, 1999     

Stochastic Multiobjective Optimization: Sample Average Approximation and Applications

We investigate one stage stochastic multiobjective optimization problems where the objectives are the expected values of random functions. Assuming that the closed form of the expected values is difficult to obtain, we apply the well known Sample Average Approximation (SAA) method to solve it. We propose a smoothing infinity norm scalarization approach to solve the SAA problem and analyse the convergence of efficient solution of the SAA problem to the original problem as sample sizes increase. Under some moderate conditions, we show that, with probability approaching one exponentially fast with the increase of sample size, an ϵ-optimal solution to the SAA problem becomes an ϵ-optimal solution to its true counterpart. Moreover, under second order growth conditions, we show that an efficient point of the smoothed problem approximates an efficient solution of the true problem at a linear rate. Finally, we describe some numerical experiments on some stochastic multiobjective optimization problems and report preliminary results.     

On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.