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

THEORETICAL COMPUTER SCIENCE 2014年第C期550卷 100-106页

作者： Haslegrave, John

Herman's self-stabilization algorithm allows a ring of N processors having any odd number of tokens to reach a stable state where exactly one token remains. McIver and Morgan conjecture that the expected time taken for stabilization is maximized when there are three equally-spaced tokens. We prove exact results on a related cost function, and obtain a bound on expected time which is very close to the conjectured bound. (C) 2014 Published by Elsevier B.V.

关键词： randomized algorithms Probabilistic self-stabilization Herman's algorithm

来源：评论

学校读者我要写书评

暂无评论

Decoupling Multi-Processors from Congestion Control in Byzantine Fault Tolerance

Decoupling Multi-Processors from Congestion Control in Byzan...

引用

2015 International Industrial Informatics and Computer Engineering Conference(IIICEC 2015)

作者： Xiang-wen LI Ling ZHOU Lian-hai YUAN The Engineering & technical College of Chengdu University of Technology

In recent years,much research has been devoted to the exploration of semaphores;unfortunately,few have investigated the deployment of randomized *** fact,few mathematicians would disagree with the improvement of Scheme,which embodies the private principles of artificial *** prove that the seminal decentralized algorithm for the improvement of fiber-optic cables by Kobayashi et *** recursively enumerable.

关键词： Multi-Processors Congestion Control Byzantine Fault Tolerance randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times

引用

SIMULATION MODELLING PRACTICE AND THEORY 2014年 46卷 101-117页

作者： Juan, Angel A. Barrios, Barry B. Vallada, Eva Riera, Daniel Jorba, Josep IN3 Open Univ Catalonia Dept Comp Sci Barcelona Spain Univ Politecn Valencia Inst Informat Technol Grp Sistemas Optimizac Aplicada E-46071 Valencia Spain

This paper describes a simulation-optimization algorithm for the Permutation Flow shop Problem with Stochastic processing Times (PFSPST). The proposed algorithm combines Monte Carlo simulation with an Iterated Local Search metaheuristic in order to deal with the stochastic behavior of the problem. Using the expected makespan as initial minimization criterion, our simheuristic approach is based on the assumption that high-quality solutions (permutations of jobs) for the deterministic version of the problem are likely to be high-quality solutions for the stochastic version - i.e., a correlation will exist between both sets of solutions, at least for moderate levels of variability in the stochastic processing times. No particular assumption is made on the probability distributions modeling each job-machine processing times. Our approach is able to solve, in just a few minutes or even less, PFSPST instances with hundreds of jobs and dozens of machines. Also, the paper proposes the use of reliability analysis techniques to analyze simulation outcomes or historical observations on the random variable representing the makespan associated with a given solution. This way, criteria other than the expected makespan can be considered by the decision maker when comparing different alternative solutions. A set of classical benchmarks for the deterministic version of the problem are adapted and tested under several scenarios, each of them characterized by a different level of uncertainty - variance level of job-machine processing times. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Permutation flow shop problem Simulation-optimization Stochastic times randomized algorithms Iterated local search Monte-Carlo simulation Reliability analysis

来源：评论

学校读者我要写书评

暂无评论

On the Road Between Robust Optimization and the Scenario Approach for Chance Constrained Optimization Problems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2014年第8期59卷 2258-2263页

作者： Margellos, Kostas Goulart, Paul Lygeros, John Swiss Fed Inst Technol Dept Informat Technol & Elect Engn Automat Control Lab CH-8092 Zurich Switzerland

We propose a new method for solving chance constrained optimization problems that lies between robust optimization and scenario-based methods. Our method does not require prior knowledge of the underlying probability distribution as in robust optimization methods, nor is it based entirely on randomization as in the scenario approach. It instead involves solving a robust optimization problem with bounded uncertainty, where the uncertainty bounds are randomized and are computed using the scenario approach. To guarantee that the resulting robust problem is solvable we impose certain assumptions on the dependency of the constraint functions with respect to the uncertainty and show that tractability is ensured for a wide class of systems. Our results lead immediately to guidelines under which the proposed methodology or the scenario approach is preferable in terms of providing less conservative guarantees or reducing the computational cost.

关键词： Chance constrained optimization randomized algorithms robust optimization scenario approach

来源：评论

学校读者我要写书评

暂无评论

Distributed Multivalued Consensus

引用

COMPUTER JOURNAL 2014年第8期57卷 1132-1140页

作者： Babaee, Arta Draief, Moez Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn Intelligent Syst & Networks Grp London SW7 2BT England

Motivated by the distributed binary consensus algorithm inPerron et al. [(2009) UsingThree States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, April, pp. 2527-2535], we propose a distributed algorithm for the multivalued consensus problem. In the multivalued consensus problem, each node initially chooses from one of k available choices and the objective of all nodes is to find the choice which was initially chosen by the majority in a distributed fashion. Although the voter model (e. g. Hassin, Y. and Peleg, D. (2002) Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput., 171, 248-268) can be used to find a consensus on multiple choices, it only guarantees consensus and not the consensus on the majority. We derive the time of convergence and an upper bound for the probability of error of our proposed algorithm which shows that, similar to Perron et al. [(2009) Using Three States for Binary Consensus on Complete Graphs. INFOCOM 2009, IEEE, pp. 2527-2535], having an additional state would result in significant improvement of both the convergence time and the probability of error for complete graphs. We also show that our algorithm could be used in Erd"s-Renyi and regular graphs by simulations.

关键词： consensus distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Design of a probabilistic robust track-following controller for hard disk drive servo systems

引用

MECHATRONICS 2014年第6期24卷 582-589页

作者： Chamanbaz, Mohammadreza Keikha, Ehsan Venkataramanan, Venkatakrishnan Al Mamun, Abdullah Wang, Qing-Guo A STAR Data Storage Inst Singapore Singapore Natl Univ Singapore Dept Elect & Comp Engn Singapore Singapore

This paper addresses the design of robust track-following dynamic output feedback controller for hard disk drives (HDDs) in face of parameter uncertainties which can enter into problem description in a possibly non-linear way. The design is performed in a probabilistic framework where the uncertain parameters are treated as random variables and the design specification is met with a given probability level. In particular, a sequential algorithm based on gradient iteration is employed to find a probabilistic robust feasible solution to the formulated problem. The design procedure is computationally tractable and its computational complexity does not depend on the number of uncertain parameters. Our case study allows natural frequency and damping ratio to vary within 8% and 10% from their nominal values for rigid body and all resonance modes. The designed controller achieves robustness in the presence of these uncertainties. Furthermore, the designed controller is implemented in real time on a commercial HDD. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Servo systems randomized algorithms Probabilistic robust design

来源：评论

学校读者我要写书评

暂无评论

SUBMODULAR FUNCTION MAXIMIZATION VIA THE MULTILINEAR RELAXATION AND CONTENTION RESOLUTION SCHEMES

引用

SIAM JOURNAL ON COMPUTING 2014年第6期43卷 1831-1879页

作者： Chekuri, Chandra Vondrak, Jan Zenklusen, Rico Univ Illinois Dept Comp Sci Urbana IL 61801 USA IBM Almaden Res Ctr San Jose CA 95120 USA ETH Dept Math CH-8092 Zurich Switzerland Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA

We consider the problem of maximizing a nonnegative submodular set function f : 2(N) -> R+ over a ground set N subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when f may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension F of f over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize F over a downward-closed polytope P described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when f is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

关键词： submodular function maximization approximation algorithms randomized algorithms contention resolution

来源：评论

学校读者我要写书评

暂无评论

Sensor networks: From dependence analysis via matroid bases to online synthesis

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期553卷 2-17页

作者： Cohen, Asaf Dolev, Shlomi Leshem, Guy Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Ashkelon Acad Coll Dept Comp Sci Ashqelon Israel

Consider the two related problems of sensor selection and sensor fusion. In the first, given a set of sensors, one wishes to identify a subset of the sensors, which while small in size, captures the essence of the data gathered by the sensors. In the second, one wishes to construct a fused sensor, which utilizes the data from the sensors (possibly after discarding dependent ones) in order to create a single sensor which is more reliable than each of the individual ones. In this work, we rigorously define the dependence among sensors in terms of joint empirical measures and incremental parsing. We show that these measures adhere to a polymatroid structure, which in turn facilitates the application of efficient algorithms for sensor selection. We suggest both a random and a greedy algorithm for sensor selection. Given an independent set, we then turn to the fusion problem, and suggest a novel variant of the exponential weighting algorithm. In the suggested algorithm, one competes against an augmented set of sensors, which allows it to converge to the best fused sensor in a family of sensors, without having any prior data on the sensors' performance. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Sensor networks Dependence analysis Polymatroids Matroid optimization randomized algorithms Greedy selection Empirical measures Lempel-Ziv Incremental parsing Online fusion

来源：评论

学校读者我要写书评

暂无评论

Auto-configuration of Physical Cell ID in LTE femtocellular systems using Self Organizing Networks

引用

WIRELESS NETWORKS 2014年第5期20卷 1107-1120页

作者： Saxena, Navrati Roy, Abhishek Kim, HanSeok Won, Jeong-Jae Sungkyunkwan Univ Suwon South Korea Samsung Elect Syst Design Lab Suwon South Korea

The commercial success of cellular networks, combined with advances in digital electronics, signal processing, and telecommunications research have lead to the design of next generation 4G-based long term evolution (LTE) wireless systems. The key essence of these emerging, LTE cellular systems lie in deployment of multiple femtocells for improved coverage and higher data rates. However, the arbitrary deployment of a wide number of femtocells makes the configuration, management and planning of LTE systems quite complex and challenging. In order to support dynamic and efficient network configuration, every cell needs to be assigned a particular Physical Cell ID (PCID). In this paper we show that the dynamic, optimal PCID allocation problem in LTE systems is NP-complete. Subsequently we provide a near-optimal solution using Self-Organizing Networks which models the problem using new merge operations and explores the search space using a suitable randomized algorithmic approach. We also discuss two feasible options for dynamic auto-configuration of the system and analyze the algorithm to prove its convergence. Simulation results point out that our proposed near-optimal solution dynamically achieves similar to 85-90 % of global optimal auto-configuration in computationally feasible time.

关键词： LTE SON Vertex coloring NP-complete Permutation randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A statistical learning theory approach for uncertain linear and bilinear matrix inequalities

引用

AUTOMATICA 2014年第6期50卷 1617-1625页

作者： Chamanbaz, Mohammadreza Dabbene, Fabrizio Tempo, Roberto Venkataramanan, Venkatakrishnan Wang, Qing-Guo Data Storage Inst Singapore Singapore Politecn Torino CNR IEIIT I-10129 Turin Italy Natl Univ Singapore Dept Elect & Comp Engn Singapore 117548 Singapore

In this paper, we consider the problem of minimizing a linear functional subject to uncertain linear and bilinear matrix inequalities, which depend in a possibly nonlinear way on a vector of uncertain parameters. Motivated by recent results in statistical learning theory, we show that probabilistic guaranteed solutions can be obtained by means of randomized algorithms. In particular, we show that the Vapnik-Chervonenkis dimension (VC-dimension) of the two problems is finite, and we compute upper bounds on it. In turn, these bounds allow us to derive explicitly the sample complexity of these problems. Using these bounds, in the second part of the paper, we derive a sequential scheme, based on a sequence of optimization and validation steps. The algorithm is on the same lines of recent schemes proposed for similar problems, but improves both in terms of complexity and generality. The effectiveness of this approach is shown using a linear model of a robot manipulator subject to uncertain parameters. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Statistical learning theory Vapnik-Chervonenkis dimension Uncertain linear/bilinear matrix inequality randomized algorithms Probabilistic design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：