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

randomized Parameterized algorithms for the Kidney Exchange Problem

algorithmS 2019年第2期12卷 50-50页

作者： Lin, Mugang Wang, Jianxin Feng, Qilong Fu, Bin Cent S Univ Sch Comp Sci & Engn Changsha 410083 Hunan Peoples R China Hengyang Normal Univ Sch Comp Sci & Technol Hengyang 421002 Peoples R China Hunan Prov Key Lab Intelligent Informat Proc & Ap Hengyang 421002 Peoples R China Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 <= L <= 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L >= 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.

关键词： kidney exchange problem randomized algorithm parameterized algorithm random partitioning multilinear monomial detection

来源：评论

学校读者我要写书评

暂无评论

randomized low-rank approximation of parameter-dependent matrices

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2024年第6期31卷

作者： Kressner, Daniel Lam, Hei Yin EPF Lausanne Inst Math CH-1015 Lausanne Switzerland

This work considers the low-rank approximation of a matrix A(t) depending on a parameter t in a compact set D subset of R-d. Application areas that give rise to such problems include computational statistics and dynamical systems. randomized algorithms are an increasingly popular approach for performing low-rank approximation and they usually proceed by multiplying the matrix with random dimension reduction matrices (DRMs). Applying such algorithms directly to A(t) would involve different, independent DRMs for every t, which is not only expensive but also leads to inherently non-smooth approximations. In this work, we propose to use constant DRMs, that is, A(t) is multiplied with the same DRM for every t. The resulting parameter-dependent extensions of two popular randomized algorithms, the randomized singular value decomposition and the generalized Nystrom method, are computationally attractive, especially when A(t) admits an affine linear decomposition with respect to t. We perform a probabilistic analysis for both algorithms, deriving bounds on the expected value as well as failure probabilities for the approximation error when using Gaussian random DRMs. Both, the theoretical results and numerical experiments, show that the use of constant DRMs does not impair their effectiveness;our methods reliably return quasi-best low-rank approximations.

关键词： dimension reduction matrix approximation numerical linear algebra randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Network Size Estimation in Small-World Networks under Byzantine Faults 33

Network Size Estimation in Small-World Networks under Byzant...

引用

33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Dept Comp Sci Houston TX 77204 USA McMaster Univ Dept Comp & Software Hamilton ON Canada

ISBN: (纸本)9781728112466

We study the fundamental problem of counting the number of nodes in a sparse network (of unknown size) under the presence of a large number of Byzantine nodes. We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power, and can deviate arbitrarily from the protocol. Essentially all known algorithms for fundamental Byzantine problems (e.g., agreement, leader election, sampling) studied in the literature assume the knowledge (or at least an estimate) of the size of the network. It is non-trivial to design algorithms for Byzantine problems that work without knowledge of the network size, especially in bounded-degree (expander) networks where the local views of all nodes are (essentially) the same and limited, and Byzantine nodes can quite easily fake the presence/absence of non-existing nodes. To design truly local algorithms that do not rely on any global knowledge (including network size), estimating the size of the network under Byzantine nodes is an important first step. Our main contribution is a randomized distributed algorithm that estimates the size of a network under the presence of a large number of Byzantine nodes. In particular, our algorithm estimates the size of a sparse, "small-world", expander network with up to O(n(1-delta)) Byzantine nodes, where n is the (unknown) network size and delta > 0 can be be any arbitrarily small (but fixed) constant. Our algorithm outputs a (fixed) constant factor estimate of log(n) with high probability;the correct estimate of the network size will be known to a large fraction ((1 - epsilon)-fraction, for any fixed positive constant) of the honest nodes. Our algorithm is fully distributed, lightweight, and simple to implement, runs in O (log(3) n) rounds, and requires nodes to send and receive messages of only small-sized messages per round;any node's local co

关键词： distributed algorithm counting byzantine behavior randomized algorithm small-world network expander

来源：评论

学校读者我要写书评

暂无评论

A fast distributed approximation algorithm for minimum spanning trees

引用

20th International Symposium on Distributed Computing

作者： Khan, Maleq Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)3540446249

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Omega(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H is an element of [1, Theta(log n)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal (O) over tilde (D(G)) time.

关键词： minimum spanning tree distributed approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

COMBINING BIASED RANDOM SAMPLING WITH METAHEURISTICS FOR THE FACILITY LOCATION PROBLEM IN DISTRIBUTED COMPUTER SYSTEMS

COMBINING BIASED RANDOM SAMPLING WITH METAHEURISTICS FOR THE...

引用

Winter Simulation Conference

作者： Cabrera, Guillem Gonzalez-Martin, Sergio Juan, Angel A. Marques, Joan M. Grasman, Scott E. Univ Oberta Catalunya IN3 Dept Comp Sci Barcelona 08018 Spain Rochester Inst Technol Ind & Syst Engn Dept Rochester NY 14623 USA

ISBN: (纸本)9781479974863

yThis paper introduces a probabilistic algorithm for solving the well-known Facility Location Problem (FLP), an optimization problem frequently encountered in practical applications in fields such as Logistics or Telecommunications. Our algorithm is based on the combination of biased random sampling -using a skewed probability distribution-with a metaheuristic framework. The use of random variates from a skewed distribution allows to guide the local search process inside the metaheuristic framework which, being a stochastic procedure, is likely to produce slightly different results each time it is run. Our approach is validated against some classical benchmarks from the FLP literature and it is also used to analyze the deployment of service replicas in a realistic Internet-distributed system.

关键词： Internet facility location randomised algorithms sampling methods statistical distributions stochastic processes FLP Internet-distributed system biased random sampling distributed computer systems facility location problem local search process metaheuristic framework optimization problem randomized algorithm service replica deployment skewed probability distribution stochastic procedure Abstracts Benchmark testing Computer architecture

来源：评论

学校读者我要写书评

暂无评论

Dynamic Maximal Matching in Clique Networks 15

Dynamic Maximal Matching in Clique Networks

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Li, Minming Robinson, Peter Zhu, Xianbin City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Augusta Univ Sch Comp & Cyber Sci Augusta GA 30912 USA

ISBN: (纸本)9783959773096

We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of edge insertions or deletions. We first show a lower bound of Q ( k) rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of Q( k rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of 0 log n) rounds, while achieving an update time that that is independent of n: In more detail, the update time is 0( N1 log k) against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes 0 ([1 log k) rounds.

关键词： distributed graph algorithm dynamic network maximal matching randomized algorithm lower bound

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Leader Election: A Chasm at Diameter Two 18

The Complexity of Leader Election: A Chasm at Diameter Two

引用

19th International Conference on Distributed Computing and Networking (ICDCN)

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Dept Comp Sci Houston TX 77204 USA Royal Holloway Univ London Dept Comp Sci Egham Surrey England

ISBN: (纸本)9781450363723

Leader election is one of the fundamental problems in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message complexity of leader election in synchronous distributed networks, in particular, in networks of diameter two. Kutten et al. [JACM 2015] showed a fundamental lower bound of Omega (m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability;this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., diameter 1), Kutten et al. [TCS 2015] established a tight bound of (Theta) over tilde(root n)(1) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of (Theta) over tilde (n) on the message complexity of leader election in diameter two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n(-c), for some positive constant c) succeeds and uses O (n log(3) n) messages and runs in O(1) rounds;this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs Omega(n) messages (even when n is known), regardless of the number of rounds. We also present an O(n log n) messages deterministic algorithm that takes O(log n) rounds (but needs knowledge of n);we show that this message complexity is tight for deterministic algorithms. Our results show that leader election can be solved in diameter two graphs in (essentially) linear (in n) message complexity and thus the Omega(m) lower bound does not apply to diamete

关键词： Distributed algorithm Leader Election randomized algorithm Message Complexity Time Complexity Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Efficiency of Distributed Random Sampling algorithm 38

Asymptotic Efficiency of Distributed Random Sampling Algorit...

引用

38th Chinese Control Conference (CCC)

作者： Liu, Qian He, Xingkang Fang, Haitao Chinese Acad Sci Acad Math & Syst Sci LSC Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China KTH Royal Inst Technol Sch Elect Engn & Comp Sci ACCESS Linnaeus Ctr SE-10044 Stockholm Sweden

ISBN: (纸本)9789881563972

In this paper, we focus on estimating the distribution of underlying parameter over random networks through reconstructing the empirical distribution of initial samples, which can be viewed as a particular average consensus problem. A class of quantized communication protocol, in which neighbors exchange information randomly selected based on the current estimate, is considered. To improve the convergence rate of this distributed random sampling algorithm, we introduce the Polyak average scheme, and show that asymptotic efficiency can be achieved through the averaging technique under proper conditions. The results show that the minimum limit covariance matrix of estimation error can be reached. i.e., the proposed algorithm achieves the highest possible rate of convergence. Finally, we provide a numerical simulation to validate the theoretical results of this work.

关键词： Average consensus distributed computation randomized algorithm asymptotic efficiency

来源：评论

学校读者我要写书评

暂无评论

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland's Rule 36

Solving Simple Stochastic Games with Few Random Nodes Faster...

引用

36th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Auger, David Coucheney, Pierre Strozecki, Yann Univ Versailles St Quentin En Yvelines DAVID Lab Versailles France

ISBN: (纸本)9783959771009

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm [21] which works in expected 2(O(root n)) time. We first give a simpler iterative variant of this algorithm, using Bland's rule from the simplex algorithm, which uses exponentially less random bits than Ludwig's version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [15] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2(O(k)), and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

关键词： simple stochastic games randomized algorithm parametrized complexity strategy improvement Bland's rule

来源：评论

学校读者我要写书评

暂无评论

Computing the Implicit Voronoi Diagram in Triple Precision

引用

11th International Workshop on algorithms and Data Structures (WADS 2009)

作者： Millman, David L. Snoeyink, Jack Univ N Carolina Dept Comp Sci Chapel Hill NC 27599 USA

ISBN: (纸本)9783642033667

In a paper that considered arithmetic precision as a limited resource in the design and analysis of algorithms, Liotta, Preparata and Tamassia defined an "implicit Voronoi diagram" supporting logarithmic-time proximity queries using predicates of twice the precision of the input and query coordinates. They reported, however, that computing this diagram uses five times the input precision. We define a reduced-precision Voronoi diagram that similarly supports proximity queries, and describe a randomized incremental construction using only three times the input precision. The expected construction time is O(n(log n + log mu)), where mu is the length of the longest Voronoi edge;we can construct the implicit Voronoi from the reduced-precision Voronoi in linear time.

关键词： Voronoi diagram Low-degree primitives randomized algorithm Robust computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：