Bounding the Expected Length of Longest Common Subsequences and Forests

We present improvements to two techniques to find lower and upper bounds for the expected length of longest common subsequences and forests of two random sequences of the same length, over a fixed size, uniformly distributed alphabet. We emphasize the power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary, we obtain some new lower and upper bounds for the problems addressed as well as some new exact results for short sequences. Received November 1996, and in final form October 1998.     

n中取连续k系统

本文介绍八十年代初诞生的一种新的系统可靠性模型--n中取连续k系统.文中对新 模型的定义、系统可靠度的精确公式、递推公式、近似公式、上下界估计式等进行了阐述;并对 其最优化问题的若干理论问题作了归纳.     

General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting

We derive general bounds on the complexity of learning in the statistical query (SQ) model and in the PAC model with classification noise. We do so by considering the problem of boosting the accuracy of weak learning algorithms which fall within the SQ model. This new model was introduced by Kearns to provide a general framework for efficient PAC learning in the presence of classification noise. We first show a general scheme for boosting the accuracy of weak SQ learning algorithms, proving that weak SQ learning is equivalent to strong SQ learning. The boosting is efficient and is used to show our main result of the first general upper bounds on the complexity of strong SQ learning. Since all SQ algorithms can be simulated in the PAC model with classification noise, we also obtain general upper bounds on learning in the presence of classification noise for classes which can be learned in the SQ model.     

New closed-form bounds on the partition function

Estimating the partition function is a key but difficult computation in graphical models. One approach is to estimate tractable upper and lower bounds. The piecewise upper bound of Sutton et al. is computed by breaking the graphical model into pieces and approximating the partition function as a product of local normalizing factors for these pieces. The tree reweighted belief propagation algorithm (TRW-BP) by Wainwright et al. gives tighter upper bounds. It optimizes an upper bound expressed in terms of convex combinations of spanning trees of the graph. Recently, Globerson et al. gave a different, convergent iterative dual optimization algorithm TRW-GP for the TRW objective. However, in many practical applications, particularly those that train CRFs with many nodes, TRW-BP and TRW-GP are too slow to be practical. Without changing the algorithm, we prove that TRW-BP converges in a single iteration for associative potentials, and give a closed form for the solution it finds. The closed-form solution obviates the need for complex optimization. We use this result to develop new closed-form upper bounds for MRFs with arbitrary pairwise potentials. Being closed-form, they are much faster to compute than TRW-based bounds. We also prove similar convergence results for loopy belief propagation (LBP) and use it to obtain closed-form solutions to the LBP pseudomarginals and approximation to the partition function for associative potentials. We then use recent results proved by Wainwright et al for binary MRFs to obtain closed-form lower bounds on the partition function. We then develop novel lower bounds for arbitrary associative networks. We report on experiments with synthetic and real-world graphs. Our new upper bounds are considerably tighter than the piecewise bounds in practice. Moreover, we can compute our bounds on several graphs where TRW-BP does not converge. Our novel lower bound, in spite of being closed-form and much faster to compute, outperforms more complicated popular algorithms for computing lower bounds like mean-field on densely connected graphs by wide margins although it does worse on sparsely connected graphs like chains.     

A probabilistic approach to problems parameterized above or below tight bounds

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds or below tight upper bounds. To illustrate the approach we consider two problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar [M. Mahajan, V. Raman, S. Sikdar, Parameterizing above or below guaranteed values, J. Comput. System Sci. 75 (2) (2009) 137–153]. We show that a generalization of one of the problems and three non-trivial special cases of the other problem admit kernels of quadratic size. As a byproduct we obtain a new probabilistic inequality that could be of independent interest. Our new inequality is dual to the Hypercontractive Inequality.     

Estimating the conservatism of Popov''s criterion for real parametric uncertainties

We consider the problems of robust stability and performance analysis of linear systems subject to parametric uncertainties. The Popov criterion provides lower bounds of stability margins and upper bounds on robust performance. In this paper we propose a method for obtaining upper bounds on stability margin or lower bounds on robust H₂ performance based on the outcome of the lower bound computation for the stability problem or the upper bound computation for the H₂ performance problem. We make several numerical tests.     

Non-asymptotic confidence bounds for the optimal value of a stochastic program

We discuss a general approach to building non-asymptotic confidence bounds for Stochastic Optimization problems. Our principal contribution is the observation that a Sample Average Approximation of a problem supplies upper and lower bounds for the optimal value of the problem which are essentially better than the quality of the corresponding optimal solutions. At the same time, such bounds are more reliable than ‘standard’ confidence bounds obtained through the asymptotic approach. We also discuss bounding the optimal value of MinMax Stochastic Optimization and stochastically constrained problems. We conclude with a simulation study illustrating the numerical behaviour of the proposed bounds.     

Improved upper bounds for the mixed structured singular value

In this paper, we take a new look at the mixed structured singular value problem, a problem of finding important applications in robust stability analysis. Several new upper bounds are proposed using a very simple approach which we call the multiplier approach. These new bounds are convex and computable by using linear matrix inequality (LMI) techniques. We show, most importantly, that these upper bounds are actually lower bounds of a well-known upper bound which involves the so-called D-scaling (for complex perturbations) and G-scaling (for real perturbations)     

Workload bounds in fluid models with priorities

In this paper we establish upper and lower bounds on the steady-state per-class workload distributions in a single-server queue with multiple priority classes. Motivated by communication network applications, the model has constant processing rate and general input processes with stationary increments. The bounds involve corresponding quantities in related models with the first-come first-served discipline. We apply the bounds to support a new notion of effective bandwidths for multi-class systems with priorities. We also apply the lower bound to obtain sufficient conditions for the workload distributions to have heavy tails.     

Lower and upper bounds in zone-based abstractions of timed automata

Timed automata have an infinite semantics. For verification purposes, one usually uses zone-based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds, significantly coarser abstractions can be obtained. We show soundness and completeness of the new abstractions w.r.t. reachability and demonstrate how information about lower and upper bounds can be used to optimise the algorithm for bringing a difference bound matrix into normal form. Finally, we experimentally demonstrate that the new techniques dramatically increase the scalability of the real-time model checker UPPAAL.     

Frequency-weighted model reduction with ∞ error bounds

This paper considers frequency-weighted model reduction. The explicit lower and upper approximation error bounds are derived for certain classes of weighted model reduction problems. The approximation is based on some unweighted approximations and the error bounds are given in terms of the Hankel singular values of the weighted model.     

Scheduling of coupled tasks and one-machine no-wait robotic cells

Coupled task scheduling problems have been known for more than 25 years. Several complexity results have been established in the meantime, but the status of the identical task case remains still unsettled. We describe a new class of equivalent one-machine no-wait robotic cell problems. It turns out that scheduling of identical coupled tasks corresponds to the production of a single part type in the robotic cell. We shall describe new algorithmic procedures to solve this robotic cell problem, allowing lower and upper bounds on the production time and discussing in particular cyclic production plans.     

Learning with continuous experts using drifting games

We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for on-line learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and on-line learning algorithms. We prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. We also extend previous lower bounds to show that our upper bounds are exactly tight for sufficiently many experts. A surprising consequence of our work is that continuous experts are only as powerful as experts making binary or no prediction in each round.     

Delay‐dependent Stability and Static Output Feedback Control of 2‐D Discrete Systems with Interval Time‐varying Delays

This paper is concerned with the problems of delay‐dependent stability and static output feedback (SOF) control of two‐dimensional (2‐D) discrete systems with interval time‐varying delays, which are described by the Fornasini‐Marchesini (FM) second model. The upper and lower bounds of delays are considered. Applying a new method of estimating the upper bound on the difference of Lyapunov function that does not ignore any terms, a new delay‐dependent stability criteria based on linear matrix inequalities (LMIs) is derived. Then, given the lower bounds of time‐varying delays, the maximum upper bounds in the above LMIs are obtained through computing a convex optimization problem. Based on the stability criteria, the SOF control problem is formulated in terms of a bilinear matrix inequality (BMI). With the use of the slack variable technique, a sufficient LMI condition is proposed for the BMI. Moreover, the SOF gain can be solved by LMIs. Numerical examples show the effectiveness and advantages of our results.     

Computing on a free tree via complexity-preserving mappings

The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query-answering problems.     

Error estimates for iterative algorithms for minimizing regularized quadratic subproblems

ABSTRACT

We derive bounds for the objective errors and gradient residuals when finding approximations to the solution of common regularized quadratic optimization problems within evolving Krylov spaces. These provide upper bounds on the number of iterations required to achieve a given stated accuracy. We illustrate the quality of our bounds on given test examples.     

Online Search with Time-Varying Price Bounds

Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models.We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm with competitive ratio \(\sqrt{D}\), where D is the known duration of the game, and a nearly-optimal randomized algorithm with competitive ratio \(\frac{\ln D}{1+\ln2-\frac{2}{D}}\). We also prove that the lower bound of competitive ratios of randomized algorithms is asymptotically \(\frac{\ln D}{4}\).The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do, for instance 2.25 versus 3.77 for D=128.     

It’s a Small World for Random Surfers

We prove logarithmic upper bounds for the diameters of the random-surfer Webgraph model and the PageRank-based selection Webgraph model, confirming the small world phenomenon holds for them. In the special case when the generated graph is a tree, we provide close lower and upper bounds for the diameters of both models.     

Models of Greedy Algorithms for Graph Problems

Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2]. S. Davis’ research supported by NSF grants CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. R. Impagliazzo’s research supported by NSF grant CCR-0098197, CCR-0313241, and CCR-0515332. Views expressed are not endorsed by the NSF. Some work done while at the Institute for Advanced Study, supported by the State of New Jersey.