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

List Colouring Constants of Triangle Free Graphs

Electronic Notes in Discrete Mathematics 2008年第C期30卷 135-140页

作者： Amini, Omid Reed, Bruce École Polytechnique Projet Mascotte I3S-CNRS UNSA Sophia-Antipolis France Projet Mascotte I3S-CNRS UNSA INRIA

In this paper we prove a result about vertex list colourings which in particular shows that a conjecture of the second author (1999, Journal of Graph Theory 31, 149-153) is true for triangle free graphs of large maximum degree. There exists a constant K such that the following holds: Given a graph G and a list assignment L to vertices of G, assigning a list of available colours L (v) to each vertex v ∈ V (G), such that | L (v) | = frac(K Δ, log (Δ)), then there exists a proper list colouring of vertices of G provided that for each colour c, the graph induced by all vertices v with c ∈ L (v) is triangle free and has maximum degree at most Δ. © 2008 Elsevier B.V. All rights reserved.

关键词： Graph colouring List colouring Probabilistic method randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Replacement Paths via Fast Matrix Multiplication

Replacement Paths via Fast Matrix Multiplication

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Weimann, Oren Yuster, Raphael Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Haifa Dept Math Haifa Israel

ISBN: (纸本)9780769542447

Let G be a directed edge-weighted graph and let P be a shortest path from s to t in G. The replacement paths problem asks to compute, for every edge e on P, the shortest s-to-t path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem removing each edge e on P one at a time and computing the shortest s-to-t path each time - is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related shortest paths problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an n-vertex graph with integral edge-lengths between -M and M, we give a randomized algorithm that uses fast matrix multiplication and is sub-cubic for appropriate values of M. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires sub-quadratic time and returns the length of the shortest u-to-v path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in sub-cubic time, that answer queries in sub-quadratic time. Our results also apply for avoiding vertices rather than edges.

关键词： approximation algorithm data structure directed edge-weighted graph directed graphs distance sensitivity oracle fast matrix multiplication matrix algebra randomised algorithms randomized algorithm replacement path sub-quadratic time

来源：评论

学校读者我要写书评

暂无评论

A Randomized Probing Scheme for Increasing the Stability Region of Multicarrier Systems

A Randomized Probing Scheme for Increasing the Stability Reg...

引用

IEEE International Symposium on Information Theory Proceedings (ISIT)

作者： Destounis, Apostolos Assaad, Mohamad Debbah, Merouane Sayadi, Bessem Alcatel-Lucent Bell Labs France|c|

ISBN: (纸本)9781479904464

In this work we address the problem of channel probing in a multicarrier downlink wireless network where in order to collect CSI feedback from each user at a channel, a fraction of the available time for transmission is used. This means that the time left to transmit is getting smaller. We study the aspect of stability of such a system and we find a randomized algorithm which can guarantee an expansion of the stability region with respect to full probing and prior works. In addition, we investigate a special case of a probing scheme that does not require knowledge of the statistics of the channels and can still enlarge the stability region of the system. Simulations show the performance of the proposed scheme.

关键词： feedback radio links radio networks radio transmitters random processes randomised algorithms stability statistics wireless channels

来源：评论

学校读者我要写书评

暂无评论

A Simulation-Based Approach for Control Design of Uncertain UAVs

A Simulation-Based Approach for Control Design of Uncertain ...

引用

51st IEEE Annual Conference on Decision and Control (CDC)

作者： Capello, Elisa Tempo, Roberto Politecn Torino Dept Mech & Aerosp Engn Corso Duca Abruzzi 24 I-10129 Turin Italy Politecn Torino CNR IEIIT I-10129 Turin Italy

ISBN: (纸本)9781467320665

The objective of this paper is the development of a randomized Linear Quadratic Regulator (LQR) algorithm via gradient-based methods for Unmanned Aerial Vehicles (UAVs) subject to uncertainty to cope with different operating conditions. A controller gain is synthesized using a Lyapunov approach dealing with a formation of two mini-UAV systems in the classical Leader/Wingman configuration. The advantages of the proposed technique over the existing deterministic methods for control design are as follows: (i) the uncertainty structure is not defined a priori and (ii) one Lyapunov inequality is approximately solved at each iteration of the algorithm, so that the number of inequalities does not grow with the number of uncertain parameters. The main contribution of this paper is to demonstrate that the proposed sequential algorithm provides a randomized controller which stabilizes the uncertain system. This probabilistic technique is then validated with an extensive a posteriori analysis. The final result is to show that the UAV reaches the desired altitude without an additional Proportional-Integral-Derivative (PID) channel, and therefore tuning of the controller gains is avoided.

关键词： Lyapunov methods approximation theory autonomous aerial vehicles control system synthesis deterministic algorithms gradient methods iterative methods linear quadratic control probability random processes randomised algorithms stability uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the Data Exchange Problem under Fairness Constraints

Efficient Algorithms for the Data Exchange Problem under Fai...

引用

50th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

作者： Milosavljevic, Nebojsa Pawar, Sameer Gastpar, Michael Ramchandran, Kannan Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9781467345392;9781467345378

In this paper we study the data exchange problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is to minimize the sum of convex functions over the number of bits each user has to transmit in order to achieve the goal. A special case of this objective is the uniform cost, which essentially leads to a "fair" communication load distribution among the users. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the users' side-information consists of subsets of the file packets;and (ii) side-information in the form of linearly correlated packets, where the users have access to linear combinations of the file packets. We provide a polynomial-time deterministic algorithm that finds an optimal communication scheme w.r.t. the transmission cost. To further lower the complexity, we also give a simple randomized algorithm inspired by our deterministic algorithm.

关键词： communication complexity data communication deterministic algorithms linear codes minimisation packet radio networks randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Quick Detection of High-degree Entities in Large Directed Networks 14

Quick Detection of High-degree Entities in Large Directed Ne...

引用

14th IEEE International Conference on Data Mining (IEEE ICDM)

作者： Avrachenkov, K. Litvak, N. Prokhorenkova, L. Ostroumova Suyargulova, E. Inria Rocquencourt France Univ Twente NL-7500 AE Enschede Netherlands Yandex Moscow Russia

ISBN: (纸本)9781479943036

In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collect and update statistics about popular entities, usually using the degree of an entity as an approximation of its popularity. We suggest a simple, efficient, and easy to implement two-stage randomized algorithm that provides highly accurate solutions to this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-00 most followed users, with more than 90% precision, in the online social network Twitter with approximately a billion of registered users. Our algorithm significantly outperforms existing methods and serves many different purposes such as finding the most popular users or the most popular interest groups in social networks. An important contribution of this work is the analysis of the proposed algorithm using Extreme Value Theory - a branch of probability that studies extreme events and properties of largest order statistics in random samples. Using this theory we derive an accurate prediction for the algorithm's performance and show that the number of API requests for finding the top-k most popular entities is sublinear in the number of entities. Moreover, we formally show that the high variability of the entities, expressed through heavy-tailed distributions, is the reason for the algorithm's efficiency. We quantify this phenomenon in a rigorous mathematical way.

关键词： application program interfaces randomised algorithms social networking (online) API requests approximation extreme value theory high-degree entities large directed networks online social network Twitter online social networks quick detection randomized algorithm statistics top-k most popular entities Algorithm design and analysis Approximation algorithms Indexes Peer-to-peer computing Prediction algorithms Twitter social networks sublinear complexity

来源：评论

学校读者我要写书评

暂无评论

Delaunay triangulations on the word RAM: Towards a practical worst-case optimal algorithm

Delaunay triangulations on the word RAM: Towards a practical...

引用

10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)

作者： Schrijvers, Okke van Bommel, Frits Buchin, Kevin Stanford Univ Comp Sci Dept Palo Alto CA 94304 USA Tech Univ Eindhoven Dept Math & Comp Sci Eindhoven Netherlands

ISBN: (纸本)9780769550374

The Delaunay triangulation of n points in the plane can be constructed in o(n log n) time when the coordinates of the points are integers from a restricted range. However, algorithms that are known to achieve such running times had not been implemented so far. We explore ways to obtain a practical algorithm for Delaunay triangulations in the plane that runs in linear time for small integers. For this, we first implement and evaluate two variants of BrioDC, an algorithm that is known to achieve this bound. We implement the first O(n)-time algorithm for constructing Delaunay triangulations and found that our implementations are practical. While we do not improve upon fast existing algorithms (with non-optimal worst-case running time) for realistic data sets, our BrioDC implementations do give us insight into the optimal time needed for point location. Secondly, we implement and evaluate variants of BRIO, an algorithm which has an O (n log n) worst-case running time on small integers but runs faster for many distributions. Our variants aim to avoid bad worst-case behavior, which is due to high point location time. Our BrioDC implementation shows that point location time can be reduced by 25% and our squarified space-filling curve orders show the first improvement by reducing this by 3%.

关键词： computational complexity curve fitting mesh generation optimisation randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Model Repair for Markov Decision Processes

Model Repair for Markov Decision Processes

引用

7th International Symposium on Theoretical Aspects of Software Engineering (TASE)

作者： Chen, Taolue Hahn, Ernst Moritz Han, Tingting Kwiatkowska, Marta Qu, Hongyang Zhang, Lijun Univ Oxford Dept Comp Sci Oxford OX1 2JD England Univ Sheffield Dept Automat Control & Systems Engn Sheffield S10 2TN S Yorkshire England Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100864 Peoples R China

ISBN: (纸本)9780769550534

Markov decision processes (MDPs) are often used for modelling distributed systems with probabilistic failure or randomisation. We consider the problem of model repair for MDPs defined as follows: if the MDP fails to satisfy a property, we aim to find new values for the transition probabilities so that the property is guaranteed to hold, while at the same time the cost of repair is minimised. Because solving the MDP repair problem exactly is infeasible, in this paper we focus on approximate solution methods. We first formulate a region-based approach, which yields an interval in which the minimal repair cost is contained. As an alternative, we also consider sampling-based approaches, which are faster but unable to provide lower bounds on the repair cost. We have integrated both methods into the probabilistic model checker PRISM and demonstrated their usefulness in practice using a computer virus case study.

关键词： Markov processes computer viruses failure analysis formal verification probability randomised algorithms sampling methods software reliability

来源：评论

学校读者我要写书评

暂无评论

A Randomized Approach to the Capacity of Finite-State Channels

A Randomized Approach to the Capacity of Finite-State Channe...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Han, Guangyue Univ Hong Kong Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781479904464

Inspired by the ideas from the field of stochastic approximation, we propose a randomized algorithm to compute the capacity of a finite-state channel with a Markovian input. When the mutual information rate of the channel is concave with respect to the chosen parameterization, we show that, at least for some practical channels, the proposed algorithm will converge to the capacity almost surely.

关键词： Markov processes approximation theory channel capacity randomised algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Validation of a Stochastic Kinematic Model for an Eight-legged Robot

Probabilistic Validation of a Stochastic Kinematic Model for...

引用

IEEE International Conference on Robotics and Automation (ICRA)

作者： Karydis, Konstantinos Poulakakis, Ioannis Tanner, Herbert G. Univ Delaware Dept Mech Engn Newark DE 19716 USA

ISBN: (纸本)9781467356411;9781467356435

The paper suggests a new method for statistically validating, and selecting the parameters of a model for a miniature eight-legged robot. It is based on a novel adaptation of concepts and techniques originally developed in the context of robust control design using randomized algorithms. The proposed approach is data driven and offers probabilistic guarantees of model fidelity and descriptive capacity, checking models against experimental data. In principle, this method applies to a large class of physical processes, the available models of which may be in a variety of forms including sets of differential equations.

关键词： control system synthesis differential equations legged locomotion probability randomised algorithms robot kinematics robust control stochastic processes

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：