检索结果-内蒙古大学图书馆

A probabilistic ellipsoid algorithm for linear optimization problems with uncertain LMI constraints

AUTOMATICA 2015年 52卷 248-254页

作者： Ataei, Armin Wang, Qian Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA Penn State Univ Dept Mech & Nucl Engn University Pk PA 16802 USA

In this paper, a probabilistic algorithm based on the deep cut ellipsoid method is proposed to solve a linear optimization problem subject to an uncertain linear matrix inequality (LMI). First, a deep cut ellipsoid algorithm is introduced to address probabilistic feasibility of the uncertain LMI. Objective cuts are then defined to search for the optimal solution. The final probabilistic ellipsoid algorithm is a combination of feasibility cuts and objective cuts. It is shown that in a finite number of iterations, the ellipsoid algorithm either returns a suboptimal probabilistically feasible solution with a high confidence level or finds the problem infeasible. Furthermore, the bounds of the suboptimal value are provided with probabilistic guarantees. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Linear matrix inequalities randomized algorithms Uncertain systems Ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

引用

ALGORITHMICA 2015年第2期72卷 607-619页

作者： Lingas, Andrzej Persson, Mia Lund Univ Dept Comp Sci S-22100 Lund Sweden Malmo Univ Dept Comp Sci S-20506 Malmo Sweden

We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.

关键词： Maximum integral flow Minimum-cost flow Polynomial verification Parallel algorithms randomized algorithms Time complexity Processor complexity

来源：评论

学校读者我要写书评

暂无评论

On the probabilistic closure of the loose unambiguous hierarchy

引用

INFORMATION PROCESSING LETTERS 2015年第9期115卷 725-730页

作者： Hirsch, Edward A. Sokolov, Dmitry Russian Acad Sci Steklov Inst Math St Petersburg St Petersburg 191023 Russia

Unambiguous hierarchies [1-3] are defined similarly to the polynomial hierarchy;however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy prUH. with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that miss the promise set;however, the oracle answer in this case can be arbitrary (a similar definition of oracle access has been used in [4]). In this short note we prove that the first part of Toda's theorem PH subset of BP . circle plus DP subset of P-PP can be strengthened to PH = BP . prUH., that is, the closure of our hierarchy under Schoning's BP operator equals the polynomial hierarchy. It is easily seen that BP . prUH. subset of BP . circle plus P. The proof follows the same lines as Toda's proof, so the main contribution of the present note is a new definition that allows to characterize PH as a probabilistic closure of unambiguous computations. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Computational complexity randomized algorithms Unambiguous computations Toda's theorem

来源：评论

学校读者我要写书评

暂无评论

Fitness Probability Distribution of Bit-Flip Mutation

引用

EVOLUTIONARY COMPUTATION 2015年第2期23卷 217-248页

作者： Chicano, Francisco Sutton, Andrew M. Whitley, L. Darrell Alba, Enrique Univ Malaga Dept Lenguajes & Ciencias Computac E-29071 Malaga Spain Univ Jena Fak Math & Informat D-07745 Jena Germany Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

关键词： Bit-flip mutation evolutionary algorithms landscape theory combinatorial optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Content Placement and Service Scheduling in Femtocell Caching Networks

Content Placement and Service Scheduling in Femtocell Cachin...

引用

IEEE Global Communications Conference

作者： Teng Liu Alhussein A. Abouzeid Department of Electrical Computer and Systems Engineering Rensselaer Polytechnic Institute

ISBN: (纸本)9781509013296

This work considers the joint problem of content placement and service scheduling in femtocell caching networks, to maximize the traffic volume served from the cache. The problem is modeled as a Markov decision process. We combine the Edmonds-Karp algorithm and the marginal allocation algorithm to develop an efficient centralized policy called Infinite CAche-filling (ICA), which can get arbitrarily close to optimal asymptotically as the estimation time window increases. We also design a randomized algorithm called Infinite CAche-filling with Probabilistic scheduling (ICAP) that takes into consideration the femtocells service capability due to interference or multiplexing techniques. We derive a lower bound on the expected discounted hit count of ICAP. We also derive an upper bound on the probability that the performance of ICAP degrades from this expected value. Numerical results show that ICAP scales well and converges relatively fast in response to request pattern changes.

关键词： Content-centric networking Femtocell network Markov decision process randomized algorithm randomized algorithms Markov chain Femtocell networks Femtocells Allocation Algorithm Cache memory Traffic volume Content distribution

来源：评论

学校读者我要写书评

暂无评论

Approximating the k-Level in Three-Dimensional Plane Arrangements 16

Approximating the k-Level in Three-Dimensional Plane Arrange...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Sariel Har-Peled Haim Kaplan Micha Sharir Department of Computer Science University of Illinois School of Computer Science Tel Aviv University

ISBN: (纸本)9781510819672

Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a O(1/r)-cutting of the first n/r levels of A(H), which consists of O(r) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the (n/r)-level by a terrain consisting of O(r/ε~3) triangular faces, which lies entirely between the levels (1 ± ε)n/r. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, that computes the terrain in O(n + r~2ε~(-6) log~3 r) expected time. An application of this technique allows us to mimic Matousek's construction of cuttings in the plane [36], to obtain a similar construction of "layered" (1/r)-cutting of the entire arrangement A(H), of optimal size O(r~3). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

关键词： terrains randomized algorithms plane landscapes Planar Proof Three Dimensions constructivity Platanus hybrida Planing Structural properties Cuttings Cutting approximation

来源：评论

学校读者我要写书评

暂无评论

Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2015年第4期22卷 647-667页

作者： Juan, Angel A. Pascual, Inaki Guimarans, Daniel Barrios, Barry Open Univ Catalonia Dept Comp Sci IN3 Barcelona Spain Natl ICT Australia Sydney NSW Australia

This paper proposes a hybrid approach for solving the multidepot vehicle routing problem (MDVRP) with a limited number of identical vehicles per depot. Our approach, which only uses a few parameters, combines biased randomizationuse of nonsymmetric probability distributions to generate randomnesswith the iterated local search (ILS) metaheuristic. Two biased-randomized processes are employed at different stages of the ILS framework in order to (a) assign customers to depots following a randomized priority criterionthis allows for fast generation of alternative allocation maps and (b) improving routing solutions associated with a promising allocation mapthis is done by randomizing the classical savings heuristic. These biased-randomized processes rely on the use of the geometric probability distribution, which is characterized by a single and bounded parameter. Being an approach with few parameters, our algorithm does not require troublesome fine-tuning processes, which tend to be time consuming. Using standard benchmarks, the computational experiments show the efficiency of the proposed algorithm. Despite its hybrid nature, our approach is relatively easy to implement and can be parallelized in a very natural way, which makes it an interesting alternative for practical applications of the MDVRP.

关键词： multidepot vehicle routing problem metaheuristics randomized algorithms biased randomization iterated local search parallelization of heuristics

来源：评论

学校读者我要写书评

暂无评论

Improved analysis of D²-sampling based PTAS for k-means and other clustering problems

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 100-103页

作者： Jaiswal, Ragesh Kumar, Mehul Yadav, Pulkit IIT Delhi Dept Comp Sci & Engn Delhi India

We give an improved analysis of the simple D-2-sampling based PTAS for the k-means clustering problem given by Jaiswal et al. [3]. The improvement on the running time is from O (nd . 2((O) over tilde) ((k2/epsilon))) ... 详细信息

关键词： randomized algorithms k-Means clustering PTAS D-2-sampling

来源：评论

学校读者我要写书评

暂无评论

A Faster Subquadratic Algorithm for Finding Outlier Correlations 16

A Faster Subquadratic Algorithm for Finding Outlier Correlat...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Matti Karppa Petteri Kaski Jukka Kohonen Department of Computer Science Aalto University

ISBN: (纸本)9781510819672

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 < τ < ρ < 1. Improving on an algorithm of G. Valiant [FOCS 2012; *** 2015], we present a randomized algorithm that for Boolean inputs ({-1, 1}-valued data normalized to unit Euclidean length) runs in time O(n~(max {1-γ+M(Δγ,γ), M(1-γ,2Δγ)}) + qdn~(2γ)), where 0 < γ < 1 is a constant tradeoff parameter and M(μ, ν) is the exponent to multiply an [n~μ] × [n~ν] matrix with an [n~ν] × [n~μ] matrix and Δ = 1/(1 - log_τ ρ). As corollaries we obtain randomized algorithms that run in time O(n(2ω)/(3-log_τ ρ) + qdn(2(1-log_τ ρ))/(3-log_τ ρ)) and in time O(n4/(2+α(1 - log_τ ρ)) + qdn(2α(1 - log_τ ρ))/(2+α(1 - log_τ ρ))), where 2 ≤ ω < 2.38 is the exponent for square matrix multiplication and 0.3 < α ≤ 1 is the exponent for rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation O (·) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ.)

关键词： Exponent randomized algorithms Dot product outliers Matrix multiplication Absolute value correlated variables Pairwise error probability Multiplication Corollary algorithms

来源：评论

学校读者我要写书评

暂无评论

Assessing Stochastic algorithms for Large Scale Nonlinear Least Squares Problems Using Extremal Probabilities of Linear Combinations of Gamma Random Variables

引用

SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION 2015年第1期3卷 61-90页

作者： Roosta-Khorasani, Farbod Szekely, Gabor J. Ascher, Uri M. Univ British Columbia Dept Comp Sci Vancouver BC V6T 1Z4 Canada Natl Sci Fdn Arlington VA 22230 USA Hungarian Acad Sci Alfred Renyi Inst Math H-1053 Budapest Hungary

This paper considers stochastic algorithms for efficiently solving a class of large scale nonlinear least squares (NLS) problems which frequently arise in applications. We propose eight variants of a practical randomized algorithm where the uncertainties in the major stochastic steps are quantified. Such stochastic steps involve approximating the NLS objective function using Monte Carlo methods, and this is equivalent to the estimation of the trace of corresponding symmetric positive semidefinite matrices. For the latter, we prove tight necessary and sufficient conditions on the sample size (which translates to cost) to satisfy the prescribed probabilistic accuracy. We show that these conditions are practically computable and yield small sample sizes. They are then incorporated in our stochastic algorithm to quantify the uncertainty in each randomized step. The bounds we use are applications of more general results regarding extremal tail probabilities of linear combinations of gamma distributed random variables. We derive and prove new results concerning the maximal and minimal tail probabilities of such linear combinations, which can be considered independently of the rest of this paper.

关键词： randomized algorithms inverse problems Monte Carlo methods trace estimation gamma random variable extremal probability large scale simulation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：