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

Linear Inflation Rules for the Random Yield Problem: Analysis and Computations

OPERATIONS RESEARCH 2010年第1期58卷 244-251页

作者： Huh, Woonghee Tim Nagarajan, Mahesh Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Univ British Columbia Operat & Logist Div Sauder Sch Business Vancouver BC V6T 1Z2 Canada

In this paper, we propose a simple heuristic approach for the inventory control problem with stochastic demand and multiplicative random yield. Our heuristic tries to find the best candidate within a class of policies that are referred to in the literature as the linear inflation rule (LIR) policies. Our approach is computationally fast, easy to implement, and intuitive to understand. Moreover, we find that in a significant number of instances our heuristic performs better than several other well-known heuristics that are available in the literature.

关键词： Inventory control Heuristic Uncertainty Stochastic models Studies randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Communication Complexity and Energy Efficient Consensus Algorithm

引用

IFAC Proceedings Volumes 2010年第19期43卷 209-214页

作者： Yilin Mo Bruno Sinopoli Carnegie Mellon University Pittsburgh PA 15213 USA

In this paper, we analyze distributed average consensus algorithms, both deterministic and gossip based, with respect to a new metric related to the energy cost of communication among agents. We first introduce a new notion of communication complexity as a metric to assess the energy efficiency properties of consensus algorithms. We provide explicit formulas to compute the communication complexity of deterministic algorithms and gossip based algorithms depending on different stopping criteria. We also show that the gossip based algorithms have less communication complexity than the deterministic counterparts under mild conditions, usually satisfied by a large number of networks. We also show that the gossip algorithm with minimum communication complexity can be effectively computed as the solution of a convex optimization problem.

关键词： Consensus algorithms randomized algorithms Communication Complexity

来源：评论

学校读者我要写书评

暂无评论

An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem 10

An O(log n/log log n)-approximation Algorithm for the Asymme...

引用

Annual ACM-SIAM Symposium on Discrete algorithms

作者： Arash Asadpour Michel X. Goemans Aleksander Madry Shayan Oveis Gharan Amin Saberi Stanford University MIT

We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/log log n) of the optimum with hig... 详细信息

ISBN: (纸本)9780898716986

关键词： travelling salesman problems Triangle inequality randomized algorithms logarithm (log) logs Optimum

来源：评论

学校读者我要写书评

暂无评论

Towards power-sensitive communication on a multiple-access channel

Towards power-sensitive communication on a multiple-access c...

引用

IEEE International Conference on Distributed Computing Systems

作者： Gianluca De Marco Dariusz R. Kowalski Dipartimento di Informatica e Applicazioni Universita di Salerno University of Liverpool

ISBN: (纸本)9781424472611;9780769540597

We are given n stations of which k are active, while the remaining n - k are asleep. The active stations communicate via a multiple-access channel. If a subset Q of active stations transmits in the same round, all active stations can recognize from the signal strength how many stations have transmitted (i.e., they learn the size of set Q), even though they may not be able to decode the contents of transmitted messages. The goal is to let each active station to learn about the set of all active stations. It is well known that Θ(klog_(k+1)n) rounds are enough, even for non-adaptive deterministic algorithms. A natural interesting generalization arises when we are required to identify a subset of m ≤ k active stations. We show that while for randomized or for adaptive deterministic algorithms _(m log_(m+1) n) rounds are sufficient, the non-adaptive deterministic counterpart still requires Θ(klog_(k+1)n) rounds;therefore, finding any subset of active stations is not easier than finding all of them by a non-adaptive deterministic algorithm. We prove our results in the more general framework of combinatorial search theory, where the problem of identifying active stations on a multiple-access channel can be viewed as a variant of the well-known counterfeit coin problem.

关键词： Multiple-access channel Distributed learning randomized algorithms Combinatorial search theory Multiple Access Channel randomized algorithms STATIONS multiple access Distance learning deterministic algorithms Active Access Channels Subset Signal Intensity Rounding off

来源：评论

学校读者我要写书评

暂无评论

Deterministic algorithms for the Lovasz Local Lemma 10

Deterministic Algorithms for the Lovasz Local Lemma

引用

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

作者： Karthekeyan Chandrasekaran Navin Goyal Bernhard Haeupler Georgia Institute of Technology Microsoft Research Massachusetts Insititute of Technology

ISBN: (纸本)9780898717013

The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d≤2~k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser.

关键词： deterministic algorithms low light Lemma formula Probability Theory Nonzero Probability of disjoint events Probability of whole sample space Probability of null event randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybrid System Identification: An SDP Approach

Hybrid System Identification: An SDP Approach

引用

2010 49th IEEE Conference on Decision and Control

作者： C. Feng C. M. Lagoa N. Ozay M. Sznaier Department of Electrical Engineering The Pennsylvania State University University Park PA 16802 USA ECE Department Northeastern University Boston MA 02115 USA

ISBN: (纸本)9781424477456

The problem of identifying discrete time affine hybrid systems with noisy measurements is addressed in this paper. Given a finite number of measurements of input/output and a bound on the measurement noise, the objective is to identify a switching sequence and a set of affine models that are compatible with the a priori information, while minimizing the number of affine models. While this problem has been successfully addressed in the literature if the input/output data is noise-free or corrupted by process noise, results for the case of measurement noise are limited, e.g., a randomized algorithm has been proposed in a previous paper [3]. In this paper, we develop a deterministic approach. Namely, by recasting the identification problem as polynomial optimization, we develop deterministic algorithms, in which the inherent sparse structure is exploited. A finite dimensional semi-definite problem is then given which is equivalent to the identification problem. Moreover, to address computational complexity issues, an equivalent rank minimization problem subject to deterministic LMI constraints is provided, as efficient convex relaxations for rank minimization are available in the literature. Numerical examples are provided, illustrating the effectiveness of the algorithms.

关键词： Noise measurement In-law hybrid systems deterministic algorithms Affine randomized algorithms noise-free Equivalent

来源：评论

学校读者我要写书评

暂无评论

Towards Property-Based Classification of Clustering Paradigms 10

Towards Property-Based Classification of Clustering Paradigm...

引用

Annual Conference on Neural Information Processing Systems

作者： Margareta Ackerman Shai Ben-David David Loker D.R.C. School of Computer Science University of Waterloo Canada

ISBN: (纸本)9781617823800

Clustering is a basic data mining task with a wide variety of applications. Not surprisingly, there exist many clustering algorithms. However, clustering is an ill defined problem - given a data set, it is not clear what a "correct" clustering for that set is. Indeed, different algorithms may yield dramatically different outputs for the same input sets. Faced with a concrete clustering task, a user needs to choose an appropriate clustering algorithm. Currently, such decisions are often made in a very ad hoc, if not completely random, manner. Given the crucial effect of the choice of a clustering algorithm on the resulting clustering, this state of affairs is truly regrettable. In this paper we address the major research challenge of developing tools for helping users make more informed decisions when they come to pick a clustering tool for their data. This is, of course, a very ambitious endeavor, and in this paper, we make some first steps towards this goal. We propose to address this problem by distilling abstract properties of the input-output behavior of different clustering paradigms. In this paper, we demonstrate how abstract, intuitive properties of clustering functions can be used to taxonomize a set of popular clustering algorithmic paradigms. On top of addressing deterministic clustering algorithms, we also propose similar properties for randomized algorithms and use them to highlight functional differences between different common implementations of k-means clustering. We also study relationships between the properties, independent of any particular algorithm. In particular, we strengthen Kleinberg's famous impossibility result, while providing a simpler proof.

关键词： Clustering algorithms Cluster Analysis cluster tools randomized algorithms critical parameter

来源：评论

学校读者我要写书评

暂无评论

An improved randomized approximation algorithm for maximum triangle packing

引用

DISCRETE APPLIED MATHEMATICS 2009年第7期157卷 1640-1646页

作者： Chen, Zhi-Zhong Tanahashi, Ruka Wang, Lusheng Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of 83/43 (1 - is an element of)(approximate to 0.518(1 - is an element of)) for any constant is an element of > 0. By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of 0.5257(1 - is an element of) for any constant E > 0. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximum triangle packing Approximation algorithms randomized algorithms Maximum-weight b-matching

来源：评论

学校读者我要写书评

暂无评论

randomized Strategies for Probabilistic Solutions of Uncertain Feasibility and Optimization Problems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2009年第11期54卷 2545-2559页

作者： Alamo, Teodoro Tempo, Roberto Camacho, Eduardo F. Univ Seville Dept Ingn Sistemas & Automat Seville 41092 Spain Politecn Torino IEIIT CNR I-10129 Turin Italy

In this paper, we study two general semi-infinite programming problems by means of a randomized strategy based on statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by the control community. The first main contribution of this paper is to demonstrate that this is not necessarily the case. Utilizing as a starting point one-sided results from statistical learning theory, we obtain bounds on the number of required samples that are manageable for "reasonable" values of probabilistic confidence and accuracy. In particular, we show that the number of required samples grows with the accuracy parameter epsilon as 1/epsilon in 1/epsilon, and this is a significant improvement when compared to the existing bounds which depend on 1/epsilon(2) ln 1/epsilon(2). Secondly, we present new results for optimization and feasibility problems involving Boolean expressions consisting of polynomials. In this case, when the accuracy parameter is sufficiently small, an explicit bound that only depends on the number of decision variables, and on the confidence and accuracy parameters is presented. For convex optimization problems, we also prove that the required sample size is inversely proportional to the accuracy for fixed confidence. Thirdly, we propose a randomized algorithm that provides a probabilistic solution circumventing the potential conservatism of the bounds previously derived.

关键词： Probabilistic robustness randomized algorithms statistical learning theory uncertain systems

来源：评论

学校读者我要写书评

暂无评论

A randomized Algorithm for Online Unit Clustering

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 486-496页

作者： Chan, Timothy M. Zarrabi-Zadeh, Hamid Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the na < ve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

关键词： Online algorithms randomized algorithms Unit clustering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：