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

randomized Fixed-Parameter algorithms for the Closest String Problem

ALGORITHMICA 2016年第1期74卷 466-484页

作者： Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hiki Saitama 3500394 Japan Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Given a set of strings of equal length and an integer , the closest string problem (CSP) requires the computation of a string of length such that for each , where is the Hamming distance between and . The problem is NP-hard and has been extensively studied in the context of approximation algorithms and fixed-parameter algorithms. Fixed-parameter algorithms provide the most practical solutions to its real-life applications in bioinformatics. In this paper we develop the first randomized fixed-parameter algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their time complexities are also significantly better than the previously best known (deterministic) algorithms.

关键词： The closest string problem Fixed-parameter algorithms randomized algorithms Computational biology

来源：评论

学校读者我要写书评

暂无评论

Consensus over evolutionary graphs 16

Consensus over evolutionary graphs

引用

European Control Conference (ECC)

作者： Smyrnakis, Michalis Freris, Nikolaos M. Tembine, Hamidou New York Univ Abu Dhabi Div Engn Saadiyat Isl POB 129188 Abu Dhabi U Arab Emirates

ISBN: (纸本)9783952426982

We establish average consensus on graphs with dynamic topologies prescribed by evolutionary games among strategic agents. Each agent possesses a private reward function and dynamically decides whether to create new links and/or whether to delete existing ones in a selfish and decentralized fashion, as indicated by a certain randomized mechanism. This model incurs a time-varying and state-dependent graph topology for which traditional consensus analysis is not applicable. We prove asymptotic average consensus almost surely and in mean square for any initial condition and graph topology. In addition, we establish exponential convergence in expectation. Our results are validated via simulation studies on random networks.

关键词： Consensus Evolutionary Games Evolutionary Graphs Distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed randomized model structure selection for NARX models

引用

INTERNATIONAL JOURNAL OF ADAPTIVE CONTROL AND SIGNAL PROCESSING 2017年第12期31卷 1853-1870页

作者： Avellina, M. Brankovic, A. Piroddi, L. Politecn Milan Dipartimento Elettron Informaz & Bioingn Milan Italy

Model structure selection (MSS) is a critical problem in the nonlinear identification field. In the framework of polynomial nonlinear autoregressive [moving average] models with exogenous input variables, it is formulated as the combinatorial problem of finding the subset of regressors that yields optimal model accuracy. Increasing the set of potential model terms improves the flexibility of the model but results in a computational overload and may even jeopardize the ability of the MSS algorithm to find the optimal model. In this work, a distributed optimization scheme is developed to tackle the MSS task for large-sized candidate regressor sets. The regressor set is split among a group of independent processors, and each of them executes an MSS routine on its local subset. Then, the processors exchange information regarding the selected models, and the corresponding regressors are distributed among all the units for a new MSS round. The procedure is repeated until convergence of all processors to the same solution. Besides a drastic reduction in the computational time, thanks to the inherent parallelizability of the algorithm execution, the proposed distributed optimization scheme can also be beneficial in terms of model accuracy, due to a more efficient exploration of the search space.

关键词： distributed optimization model structure selection nonlinear model identification parallel processing polynomial NARX models randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Resource Allocation with Matching Constraints 19

Online Resource Allocation with Matching Constraints

引用

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

作者： John P. Dickerson Karthik Abinav Sankararaman Kanthi Kiran Sarpatwar Aravind Srinivasan Kun-Lung Wu Pan Xu University of Maryland College Park MD USA University of Maryland College Park College Park MD USA IBM Research AI Yorktown Heights NY USA University of Maryland College Park College Park MD USA

ISBN: (纸本)9781450363099

Matching markets with historical data are abundant in many applications, e.g., matching candidates to jobs in hiring, workers to tasks in crowdsourcing markets, and jobs to servers in cloud services. In all these applications, a match consumes one or more shared and limited resources and the goal is to best utilize these to maximize a global objective. Additionally, one often has historical data and hence some statistics (usually first-order moments) of the arriving agents (\emphe.g., candidates, workers, and jobs) can be learnt. To model these scenarios, we propose a unifying framework, called Multi-Budgeted Online Assignment with Known Adversarial Distributions. In this model, we have a set of offline servers with different deadlines and a set of online job types. At each time, a job of type j arrives. Assigning this job to a server i yields a profit $w_i, j $ while consuming $\mathbfa _e \in [0, 1]^K$ quantities of distinct resources. The goal is to design an (online) assignment policy that maximizes the total expected profit without violating the (hard) budget constraint. We propose and theoretically analyze two linear programming (LP) based algorithms which are almost optimal among all LP-based approaches. We also propose several heuristics adapted from our algorithms and compare them to other LP-agnostic algorithms using both synthetic as well as real-time cloud scheduling and public safety datasets. Experimental results show that our proposed algorithms are effective and significantly out-perform the baselines. Moreover, we show empirically the trade-off between fairness and efficiency of our algorithms which does well even on fairness metrics without explicitly optimizing for it.

关键词： online scheduling randomized algorithms fairness online matching

来源：评论

学校读者我要写书评

暂无评论

A randomized Approach to Probabilistic Footprint Estimation of a Space Debris Uncontrolled Reentry

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2017年第10期18卷 2657-2666页

作者： Falsone, Alessandro Prandini, Maria Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

This paper studies the problem of characterizing the region of the airspace that will be occupied by a space debris during an uncontrolled reentry (footprint), with the final goal of supporting the air traffic controllers in their task of guiding aircraft safely from their origin to their destination. Given the various sources of uncertainty affecting the debris dynamics, the reentry process is characterized probabilistically and the problem of determining the footprint is formulated in terms of a chance-constrained optimization program, which is solved via a simulation-based method. When observations of the debris initial position and radar measurements of the aircraft prior to the reentry event are available, nonlinear filtering techniques can be adopted and the posterior probability distribution of the debris position as well as of the wind field affecting the reentry process can be integrated in the chance-constraint formulation so as to obtain an enhanced estimate of the footprint. Simulation results show the efficacy of the approach.

关键词： randomized algorithms nonlinear filtering air traffic control uncontrolled debris reentry

来源：评论

学校读者我要写书评

暂无评论

Adaptive randomized Dimension Reduction on Massive Data

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 5134-5163页

作者： Darnell, Gregory Georgiev, Stoyan Mukherjee, Sayan Engelhardt, Barbara E. Princeton Univ Lewis Sigler Inst Princeton NJ 08544 USA Google Palo Alto CA 94043 USA Duke Univ Dept Stat Sci Durham NC 27708 USA Duke Univ Dept Math Durham NC 27708 USA Duke Univ Dept Comp Sci Durham NC 27708 USA Princeton Univ Dept Comp Sci Ctr Stat & Machine Learning Princeton NJ 08540 USA

The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduction methods. In this paper, we develop an approach for dimension reduction that exploits the assumption of low rank structure in high dimensional data to gain both computational and statistical advantages. We adapt recent randomized low-rank approximation algorithms to provide an efficient solution to principal component analysis (PCA), and we use this efficient solver to improve estimation in large-scale linear mixed models (LMM) for association mapping in statistical genomics. A key observation in this paper is that randomization serves a dual role, improving both computational and statistical performance by implicitly regularizing the covariance matrix estimate of the random effect in an LMM. These statistical and computational advantages are highlighted in our experiments on simulated data and large-scale genomic studies.

关键词： dimension reduction generalized eigendecompositon low-rank genomics linear mixed models supervised random projections randomized algorithms Krylov subspace methods

来源：评论

学校读者我要写书评

暂无评论

Bit-Vector Model Counting Using Statistical Estimation 24th

Bit-Vector Model Counting Using Statistical Estimation

引用

24th International Conference on Tools and algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the 21st European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Kim, Seonmo McCamant, Stephen Univ Minnesota Minneapolis MN 55455 USA

ISBN: (纸本)9783319899602;9783319899596

Approximate model counting for bit-vector SMT formulas (generalizing #SAT) has many applications such as probabilistic inference and quantitative information-flow security, but it is computationally difficult. Adding random parity constraints (XOR streamlining) and then checking satisfiability is an effective approximation technique, but it requires a prior hypothesis about the model count to produce useful results. We propose an approach inspired by statistical estimation to continually refine a probabilistic estimate of the model count for a formula, so that each XOR-streamlined query yields as much information as possible. We implement this approach, with an approximate probability model, as a wrapper around an off-the-shelf SMT solver or SAT solver. Experimental results show that the implementation is faster than the most similar previous approaches which used simpler refinement strategies. The technique also lets us model count formulas over floating-point constraints, which we demonstrate with an application to a vulnerability in differential privacy mechanisms.

关键词： Model counting Bit-vectors Floating point #SAT randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Stochastic algorithms for distributed optimization and machine learning

Stochastic algorithms for distributed optimization and machi...

引用

作者： Zhou, Yi Georgia Institute of Technology

学位级别：博士

In the big data era, machine learning acts as a powerful tool to help us make predictions and decisions. It has strong ties to the field of optimization, in the way the latter provides methods and theory. While data tends to be collected in a distributed fashion, the standard machine learning models require centralizing the training data on one machine or in a data center, which incurs significant communication cost and puts data privacy at risk. To circumvent such an issue, a variety of distributed machine learning models have been proposed and studied in the literature. In this thesis, we focus on designing and analyzing stochastic algorithms for distributed machine learning that achieve the best communication and sampling complexities. The first part of this thesis is devoted to investigating randomized incremental gradient (RIG) methods for solving the class of finite-sum optimization problems, which is the core problem in distributed optimization. By developing and proving the optimality of the primal-dual gradient method, which covers the well-known Nesterov's accelerated gradient method as a special case, we propose its randomized version, namely the randomized primal-dual gradient (RPDG) method. RPDG only involves the computation of one randomly selected component function per iteration. Moreover, by providing a lower complexity bound for the class of RIG methods for finite-sum optimization, we demonstrate the optimality of RPDG, and this is the first time such an optimal RIG method has been developed for solving finite-sum optimization problems. In the second part of this thesis, we consider a distributed topology with a central authority, and study the distributed finite-sum optimization problems defined over such a star network topology. We propose an optimal RIG method, namely the random gradient extrapolation method (RGEM) and show that it does not require any exact gradient evaluations even at the initial point, but can still achieve the optimal commun

关键词： randomized algorithms Stochastic optimization Distributed optimization Machine learning Distributed machine learning Finite-sum optimization

来源：评论

学校读者我要写书评

暂无评论

A randomized Algorithm for Optimal PID Controllers

引用

algorithms 2018年第6期11卷 81-81页

作者： Peretz, Yossi Jerusalem Coll Technol Lev Acad Ctr Dept Comp Sci POB 16031 Jerusalem Israel

A randomized algorithm is suggested for the syntheses of optimal PID controllers for MIMO coupled systems, where the optimality is with respect to the H-infinity-norm, the H-2-norm and the LQR functional, with possible system-performance specifications defined by regional pole-placement. Other notions of optimality (e.g., mixed H-2/H-infinity design, controller norm or controller sparsity) can be handled similarly with the suggested algorithm. The suggested method is direct and thus can be applied to continuous-time systems as well as to discrete-time systems with the obvious minor changes. The presented algorithm is a randomized algorithm, which has a proof of convergence (in probability) to a global optimum.

关键词： continuous-time linear systems discrete-time linear systems state-space representation proportional-integral-differential controllers static output feedbacks optimal controllers randomized algorithms convergence in probability

来源：评论

学校读者我要写书评

暂无评论

A randomized Algorithm for Prediction Interval Using RVFL Networks Ensemble 24th

A Randomized Algorithm for Prediction Interval Using RVFL Ne...

引用

24th International Conference on Neural Information Processing (ICONIP)

作者： Miskony, Bara Wang, Dianhui La Trobe Univ Dept Comp Sci & Informat Technol Melbourne Vic 3086 Australia

ISBN: (纸本)9783319700939;9783319700922

Prediction Intervals (PIs) can specify the level of uncertainty related to point-based prediction. Most Neural Network (NN)based approaches for constructing PIs suffer from computational expense and some restrictive assumptions on data distribution. This paper develops a randomized algorithm for PIs building with good performance in terms of both effectiveness and efficiency. To achieve this goal, a neural network ensemble with random weights is employed as a learner model, and a novel algorithm for generating teacher signals is proposed. Our proposed randomized Algorithm for Prediction Intervals (RAPI) constructs an NN ensemble with two outputs, representing the lower and upper bounds of PIs, respectively. Experimental results with comparisons over nine benchmark datasets indicate that RAPI performs favourably in terms of coverage rate, specificity and efficiency.

关键词： Prediction Intervals randomized algorithms Neural networks with random weights Ensemble learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：