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

A randomized algorithm for determining dominating sets in graphs of maximum degree five

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 5122-5127页

作者： Khamis, Soheir M. Daoud, Sameh S. Essa, Hanaa A. E. Ain Shams Univ Fac Sci Dept Math Div Comp Sci Cairo Egypt Tanta Univ Fac Sci Dept Math Tanta Egypt

The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum dominating set Las Vegas technique randomized algorithm Polynomial-time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A statistical perspective on algorithmic leveraging

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2015年第1期16卷

作者： Ping Ma Michael W. Mahoney Bin Yu Department of Statistics University of Georgia Athens GA International Computer Science Institute and Department of Statistics University of California at Berkeley Berkeley CA Department of Statistics University of California at Berkeley Berkeley CA

One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this *** this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance, both conditional and unconditional on the observed data. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform *** on these theoretical results, we propose and analyze two new leveraging algorithms: one constructs a smaller least-squares problem with "shrinkage" leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical results

关键词： least squares leverage scores linear regression randomized algorithm subsampling

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for the min-max selecting items problem with uncertain weights

引用

ANNALS OF OPERATIONS RESEARCH 2009年第1期172卷 221-230页

作者： Kasperski, Adam Zielinski, Pawel Wroclaw Univ Technol Inst Ind Engn & Management PL-50370 Wroclaw Poland Wroclaw Univ Technol Inst Math & Comp Sci PL-50370 Wroclaw Poland

This paper deals with the min-max version of the problem of selecting p items of the minimum total weight out of a set of n items, where the item weights are uncertain. The discrete scenario representation of uncertainty is considered. The Computational complexity of the problem is explored. A randomized algorithm for the problem is then proposed, which returns an O(ln K)-approximate Solution with a high probability, where K is the number of scenarios. This is the first approximation algorithm with better than K worst case ratio for the class of min-max combinatorial optimization problems with unbounded scenario set.

关键词： Minmax Selecting items randomized algorithm Robust optimization

来源：评论

学校读者我要写书评

暂无评论

Quantized Feedback Stabilization of Sampled-Data Switched Linear Systems

引用

IFAC Proceedings Volumes 2014年第3期47卷 9979-9984页

作者： Masashi Wakaiki Yutaka Yamamoto Graduate School of Informatics Kyoto University Kyoto 606-8501 Japan

We propose a stability analysis method for sampled-data switched linear systems with quantization. The available information to the controller is limited: the quantized state and switching signal at each sampling time. Switching between sampling times can produce the mismatch of the modes between the plant and the controller. Moreover, the coarseness of quantization makes the trajectory wander around, not approach, the origin. Hence the trajectory may leave the desired neighborhood if the mismatch leads to instability of the closed-loop system. For the stability of the switched systems, we develop a sufficient condition characterized by the total mismatch time . The relationship between the mismatch time and the dwell time of the switching signal is also discussed.

关键词： Quantization sampled-data control switched systems Lyapunov function randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

On the mean square error of randomized averaging algorithms

引用

AUTOMATICA 2013年第8期49卷 2496-2501页

作者： Frasca, Paolo Hendrickx, Julien M. Politecn Torino Dept Math Sci I-10129 Turin Italy Catholic Univ Louvain ICTEAM Inst B-1348 Louvain Belgium

This paper considers randomized discrete-time consensus systems that preserve the average "on average". As a main result, we provide an upper bound on the mean square deviation of the consensus value from the initial average. Then, we apply our result to systems in which few or weakly correlated interactions take place: these assumptions cover several algorithms proposed in the literature. For such systems we show that, when the network size grows, the deviation tends to zero, and that the speed of this decay is not slower than the inverse of the size. Our results are based on a new approach, which is unrelated to the convergence properties of the system. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Consensus algorithm randomized algorithm Networked estimation

来源：评论

学校读者我要写书评

暂无评论

Feasibility of Polynomial-Time randomized Gathering for Oblivious Mobile Robots

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2013年第4期24卷 716-723页

作者： Izumi, Taisuke Izumi, Tomoko Kamei, Sayaka Ooshita, Fukuhito Nagoya Inst Technol Grad Sch Engn Showa Ku Nagoya Aichi 4668555 Japan Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Shiga 5258577 Japan Hiroshima Univ Dept Informat Engn Fac Engn Grad Sch Engn Hiroshima 7398527 Japan Osaka Univ Grad Sch Informat Sci & Technol Suita Osaka 5650871 Japan

We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.

关键词： Distributed algorithm autonomous mobile robots gathering problem randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal measures and Markov transition kernels

引用

JOURNAL OF GLOBAL OPTIMIZATION 2013年第2期55卷 387-416页

作者： Belavkin, Roman V. Middlesex Univ Sch Engn & Informat Sci London NW4 4BT England

We study optimal solutions to an abstract optimization problem for measures, which is a generalization of classical variational problems in information theory and statistical physics. In the classical problems, information and relative entropy are defined using the Kullback-Leibler divergence, and for this reason optimal measures belong to a one-parameter exponential family. Measures within such a family have the property of mutual absolute continuity. Here we show that this property characterizes other families of optimal positive measures if a functional representing information has a strictly convex dual. Mutual absolute continuity of optimal probability measures allows us to strictly separate deterministic and non-deterministic Markov transition kernels, which play an important role in theories of decisions, estimation, control, communication and computation. We show that deterministic transitions are strictly sub-optimal, unless information resource with a strictly convex dual is unconstrained. For illustration, we construct an example where, unlike non-deterministic, any deterministic kernel either has negatively infinite expected utility (unbounded expected error) or communicates infinite information.

关键词： Expected utility Information distance Optimal policy Radon measure randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized Recovery for Boolean Compressed Sensing

Randomized Recovery for Boolean Compressed Sensing

引用

IEEE International Symposium on Information Theory Proceedings (ISIT)

作者： Fatemi, Mitra Vetterli, Martin Ecole Polytech Fed Lausanne Lab Audiovisual Commun CH-1015 Lausanne Switzerland

ISBN: (纸本)9781479904464

We consider the problem of boolean compressed sensing, which is also known as group testing. The goal is to recover a small number of defective items in a large set from a few collective binary tests. This problem can be formulated as a binary linear program, which is NP hard in general. To overcome the computational burden, it was recently proposed to relax the binary constraint on the variables, and apply a rounding to the solution of the relaxed linear program. In this paper, we introduce a randomized algorithm to replace the rounding procedure. We show that the proposed algorithm considerably improves the success rate with only a slight increase in computational cost.

关键词： Boolean compressed sensing Group testing Linear programming randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Testing consistency of quartet topologies: A parameterized approach

引用

INFORMATION PROCESSING LETTERS 2013年第22-24期113卷 852-857页

作者： Chang, Maw-Shang Lin, Chuang-Chieh Rossmanith, Peter Acad Sinica Genom Res Ctr Taipei 115 Taiwan Hungkuang Univ Dept Comp Sci & Informat Engn Taichung 43302 Taiwan RVVTH Aachen Univ Dept Comp Sci D-52056 Aachen Germany

Property testing considers the following task: given a function psi over a domain D, a property P and a parameter 0 < epsilon < 1, by querying function values of f over o(vertical bar D vertical bar) elements in D, determine if psi satisfies P or differs from any one which satisfies P in at least epsilon vertical bar D vertical bar elements. We focus on consistency of quartet topologies. Given a set Q of quartet topologies over an n-taxon set and an upper bound k on the number of quartets whose topologies are missing, we present a non-adaptive property tester with one-sided error, which runs in O(1.7321(k)kn(3)/epsilon) time and uses O(kn(3)/epsilon) queries, to test if Q is consistent with an evolutionary tree. (C) 2013 Elsevier B.V. All rights reserved.

关键词： randomized algorithm Property testing Evolutionary tree Quartet method

来源：评论

学校读者我要写书评

暂无评论

On approximating the d-girth of a graph

引用

DISCRETE APPLIED MATHEMATICS 2013年第16-17期161卷 2587-2596页

作者： Peleg, David Sau, Ignasi Shalom, Mordechai Weizmann Inst Sci IL-76100 Rehovot Israel CNRS LIRMM Montpellier France TelHai Acad Coll IL-12210 Upper Galilee Israel

For a finite, simple, undirected graph G and an integer d >= 1, a mindeg-d subgraph is a subgraph of G of minimum degree at least d. The d-girth of G, denoted by g(d)(G), is the minimum size of a mindeg-d subgraph of G. It is a natural generalization of the usual girth, which coincides with the 2-girth. The notion of d-girth was proposed by Erdos et al. (1988, 1990) [14,15] and Bollobas and Brightwell (1989) [8] over 25 years ago, and studied from a purely combinatorial point of view. Since then, no new insights have appeared in the literature. Recently, first algorithmic studies of the problem have been carried out by Amini et al. (2012a,b) [2,4]. The current article further explores the complexity of finding a small mindeg-d subgraph of a given graph (that is, approximating its d-girth), by providing new hardness results and the first approximation algorithms in general graphs, as well as analyzing the case where G is planar. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Generalized girth Minimum degree Approximation algorithm Hardness of approximation randomized algorithm Planar graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：