Search

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. [ABSTRACT FROM AUTHOR]

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of NP with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in NP and cryptanalysis of key agreement protocols in the "bounded storage model" when mixed with (time) complexity-based cryptography. [ABSTRACT FROM AUTHOR]

It is becoming increasingly apparent that probabilistic approaches can overcome conservatism and computational complexity of the classical worst-case deterministic framework and may lead to designs that are actually safer. In this paper we argue that a comprehensive probabilistic robustness analysis requires a detailed evaluation of the robustness function, and we show that such an evaluation can be performed with essentially any desired accuracy and confidence using algorithms with complexity that is linear in the dimension of the uncertainty space. Moreover, we show that the average memory requirements of such algorithms are absolutely bounded and well within the capabilities of today's computers. In addition to efficiency, our approach permits control over statistical sampling error and the error due to discretization of the uncertainty radius. For a specific level of tolerance of the discretization error, our techniques provide an efficiency improvement upon conventional methods which is inversely proportional to the accuracy level; i.e., our algorithms get better as the demands for accuracy increase. [ABSTRACT FROM AUTHOR]

Differential repetitive processes are a distinct class of continuous-discrete two-dimensional linear systems of both systems theoretic and applications interest. These processes complete a series of sweeps termed passes through a set of dynamics defined over a finite duration known as the pass length, and once the end is reached the process is reset to its starting position before the next pass begins. Moreover the output or pass profile produced on each pass explicitly contributes to the dynamics of the next one. Applications areas include iterative learning control and iterative solution algorithms, for classes of dynamic nonlinear optimal control problems based on the maximum principle, and the modeling of numerous industrial processes such as metal rolling, long-wall cutting, etc. In this paper we develop substantial new results on optimal control of these processes in the presence of constraints where the cost function and constraints are motivated by practical application of iterative learning control to robotic manipulators and other electromechanical systems. The analysis is based on generalizing the well-known maximum and ϵ-maximum principles to them. [ABSTRACT FROM AUTHOR]

This paper approaches optimal control problems for discrete-time controlled Markov processes by representing the value of the problem in a dual Lagrangian form; the value is expressed as an infimum over a family of Lagrangian martingales of an expectation of a pathwise supremum of the objective adjusted by the Lagrangian martingale term. This representation opens up the possibility of numerical methods based on Monte Carlo simulation, which may be advantageous in high-dimensional problems or in problems with complicated constraints. [ABSTRACT FROM AUTHOR]

J, J'-lossless factorization plays a central role in $H_\infty$-control because it gives a simple and unified framework of $H_\infty$-control from the viewpoint of classical network theory, and it includes the well-known inner--outer factorization of rational matrices, Wiener--Hopf factorization, and spectral factorization of positive rational matrices as special cases. However, up to now, there is still a lack of numerically reliable methods for this important factorization problem in a general setting. In this paper, we present necessary and sufficient solvability conditions and develop a numerically reliable algorithm based on a generalized eigenvalue approach for the J, J'-lossless factorization of general rational matrices. [ABSTRACT FROM AUTHOR]

We consider a countable state Markov decision process with bounded reward function and an absorbing set. At first we generalize known properties and derive new properties of the critical discount factor, which is roughly defined as the maximal discount factor under which for V, the maximal expected infinite-stage discounted reward, there is guaranteed existence, boundedness, and computability by the successive approximation method. The emphasis of the paper is on algorithms for computing V exactly (recursion in state space and policy iteration) or approximately (value iteration combined with an extrapolation and finite state approximation). Our extrapolation method is motivated by and based on the Perron--Frobenius theory for nonlinear operators. As a by-product we obtain an efficient algorithm for determining the distribution of the entrance time of a Markov chain into an absorbing set. Further results concern asymptotically $\epsilon$-optimal policies and a new turnpike theorem. Some of the results need tightness of the transition law, which turns out to be equivalent to compactness of a nonlinear operator, which is crucial for our study. [ABSTRACT FROM AUTHOR]

This paper analyzes asymptotic convergence properties of policy iteration in a class of stationary, infinite-horizon Markovian decision problems that arise in optimal growth theory. These problems have continuous state and control variables and must therefore be discretized in order to compute an approximate solution. The discretization may render inapplicable known convergence results for policy iteration such as those of Puterman and Brumelle [Math. Oper. Res., 4 (1979), pp. 60-69]. Under certain regularity conditions, we prove that for piecewise linear interpolation, policy iteration converges quadratically. Also, under more general conditions we establish that convergence is superlinear. We show how the constants involved in these convergence orders depend on the grid size of the discretization. These theoretical results are illustrated with numerical experiments that compare the performance of policy iteration and the method of successive approximations. [ABSTRACT FROM AUTHOR]