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

Broadcasting in ad hoc multiple access channels

THEORETICAL COMPUTER SCIENCE 2015年 584卷 155-176页

作者： Anantharamu, Lakshmi Chlebus, Bogdan S. Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA

We study broadcast in multiple access channels in dynamic adversarial settings. There is an unbounded supply of anonymous stations attached to a synchronous channel. There is an adversary who injects packets into stations to be broadcast on the channel. The adversary is restricted by injection rate, burstiness, and by how many passive stations can be simultaneously activated by providing them with packets. We consider deterministic distributed broadcast algorithms, which are further categorized by their properties. We investigate for which injection rates can algorithms attain bounded packet latency, when adversaries are restricted to be able to activate at most one station per round. The rates of algorithms we present make the increasing sequence consisting of 1/3, 3/8 and 1/2, reflecting the additional features of algorithms. We show that injection rate 3/4 cannot be handled with bounded packet latency. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Multiple access channel Adversarial queuing Distributed broadcast deterministic algorithm Stability Packet latency

来源：评论

学校读者我要写书评

暂无评论

Kinetic Facility Location

引用

algorithmICA 2010年第3期57卷 562-584页

作者： Degener, Bastian Gehweiler, Joachim Lammersen, Christiane Univ Bonn Comp Sci Dept 1 D-53117 Bonn Germany Univ Gesamthsch Paderborn Int Grad Sch Dynam Intelligent Syst D-33095 Paderborn Germany Univ Gesamthsch Paderborn Dept Comp Sci Heinz Nixdorf Inst D-33095 Paderborn Germany

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant. Our kinetic data structure requires O(n(log(d)(n)+ log(nR))) space in total, where R := max(pi is an element of P) f(i).max(pi is an element of P)d(i)/min(pi is an element of P) f(i).min(pi is an element of P) d(i), P = {p(1), p(2), ... , p(n)} is the set of given points, and f(i), d(i) are the maintenance cost and the demand of a point pi, respectively. In case that each trajectory can be described by a bounded degree polynomial, we process O(n(2) log(2)(nR)) events, each requiring O(log(d+1)(n).log(nR)) time and O(log(nR)) status changes.

关键词： Facility location Kinetic data structure Approximation algorithm deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE COVER TIME OF DENSE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第3期33卷 1374-1389页

作者： Cooper, Colin Frieze, Alan M. Pegden, Wesley Kings Coll London London WC2R 2LS England Carnegie Mellon Univ Dept Math Pittsburgh PA 15213 USA Carnegie Mellon Univ Math Sci Pittsburgh PA 15213 USA

We consider arbitrary graphs G with n vertices and minimum degree at least delta n where delta > 0 is constant. (a) If the conductance of G is sufficiently large, then we obtain an asymptotic expression for the cover time C-G of G as the solution to an explicit transcendental equation. (b) If the conductance is not large enough to apply (a), but the mixing time of a random walk on G is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. (c) If G fits neither (a) nor (b), then we give a deterministic asymptotic (2+o(1))-approximation of C-G.

关键词： cover time dense graphs deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Multi-bend bus-driven floorplanning considering fixed-outline constraints

引用

INTEGRATION-THE VLSI JOURNAL 2013年第2期46卷 142-152页

作者： Sheng, Wenxu Dong, Sheqin Tsinghua Univ Dept Comp Sci & Technol EDA Lab Beijing Peoples R China

The rapid rate of technological advances makes it necessary for very large scale integration (VLSI) floorplanning to consider not only interconnect constraints, but also fixed-outline constraints. In this paper, we propose a new approach to address the problem of Bus-Driven Floorplanning (BDF) within a fixed die. By providing the width and height of a chip, a set of circuit blocks and the bus specifications (i.e., the width of each bus and the blocks that the bus needs to go through), the approach will generate a final floorplan that satisfies the following requirements: (a) all blocks are packed within the fixed outline, (b) all buses are routable and (c) the floorplan area and total bus area are minimized. Based on the deterministic algorithm Less Flexibility First (LFF), our approach does not need to resort to a floorplan representation and functions very well in fixed-outline floorplanning. Our approach places no limitations on the shape of the buses, and the processes of block packing and bus packing proceed simultaneously. According to the experimental results, our approach can generate a good solution with a lower percentage of dead space, a shorter total length of all buses and a shorter run time, even under fixed-outline constraints. In addition, our algorithm works well for large and complex test cases that have not been studied in previous research. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Physical design Bus planning Fixed-outline Floorplanning deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Improving K-Nearest Neighbor Approaches for Density-Based Pixel Clustering in Hyperspectral Remote Sensing Images

引用

REMOTE SENSING 2020年第22期12卷 3745-3745页

作者： Cariou, Claude Le Moan, Steven Chehdi, Kacem Univ Rennes CNRS UMR 6164 EnssatInst Elect & Technol numeR 6 Rue Kerampont F-22300 Lannion France Massey Univ Ctr Res Image & Signal Proc Palmerston North 4410 New Zealand

We investigated nearest-neighbor density-based clustering for hyperspectral image analysis. Four existing techniques were considered that rely on a K-nearest neighbor (KNN) graph to estimate local density and to propagate labels through algorithm-specific labeling decisions. We first improved two of these techniques, a KNN variant of the density peaks clustering method dpc, and a weighted-mode variant of knnclust, so the four methods use the same input KNN graph and only differ by their labeling rules. We propose two regularization schemes for hyperspectral image analysis: (i) a graph regularization based on mutual nearest neighbors (MNN) prior to clustering to improve cluster discovery in high dimensions;(ii) a spatial regularization to account for correlation between neighboring pixels. We demonstrate the relevance of the proposed methods on synthetic data and hyperspectral images, and show they achieve superior overall performances in most cases, outperforming the state-of-the-art methods by up to 20% in kappa index on real hyperspectral images.

关键词： clustering methods density estimation nearest neighbor search deterministic algorithm unsupervised learning

来源：评论

学校读者我要写书评

暂无评论

LDPC codes based on Mobius transformations

引用

IET COMMUNICATIONS 2019年第11期13卷 1615-1624页

作者： Gholami, Mohammad Nassaj, Akram Shahrekord Univ Dept Math POB 115 Shahrekord Iran Inst Res Fundamental Sci IPM Sch Comp Sci POB 19395-5746 Tehran Iran

Recently, a class of low-density parity-check (LDPC) codes from affine permutation matrices, called APM-LDPC codes, have attracted because of some advantages rather than QC-LDPC codes in minimum-distance, girth, cycle distribution and error-rate performance. In this study, a new class of LDPC codes based on Mobius transformations, called MT-LDPC codes, are presented as a generalisation of APM-LDPC codes which have some new achievements rather than QC and APM LDPC codes in the terms of length, cycle distribution and error-rate performance. Moreover, each Mobius transformation is represented by a square matrix which is helpful to pursuing the cycles in the Tanner graph of an MT-LDPC code by the product of some square matrices. In continue, for a given base matrix, the authors propose a deterministic algorithm which efficiently produces MT-LDPC codes with the desired girth. Simulation results show that the binary and non-binary constructed MT-LDPC codes outperform APM, QC, PEG, random-like and some algebraic LDPC codes with the same rates and lengths.

关键词： cyclic codes matrix algebra parity check codes graph theory Mobius transformation low-density parity-check codes APM-LDPC codes QC-LDPC codes cycle distribution error-rate performance nonbinary constructed MT-LDPC codes algebraic LDPC codes affine permutation matrices minimum-distance square matrix Tanner graph base matrix deterministic algorithm desired girth

来源：评论

学校读者我要写书评

暂无评论

Local Deal-Agreement algorithms for Load Balancing in Dynamic General Graphs

引用

THEORY OF COMPUTING SYSTEMS 2022年第2期67卷 348-382页

作者： Dinitz, Yefim Dolev, Shlomi Kumar, Manish Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

We study the classic load balancing problem on dynamic general graphs, where the graph changes arbitrarily between the computational rounds, remaining connected with no permanent cut. A lower bound of Omega (n(2)) for the running time bound in the dynamic setting, where n is the number of nodes in the graph, is known even for randomized algorithms. We solve the problem by deterministic distributed algorithms, based on a short local deal-agreement communication of proposal/deal in the neighborhood of each node. Our synchronous load balancing algorithms achieve a discrepancy of is an element of within the time of O(nDlog(nK/is an element of)) for the continuous setting and the discrepancy of at most 2D within the time of O(nDlog(nK/D)) and a 1-balanced state within the additional time of O(nD(2)) for the discrete setting, where K is the initial discrepancy, and D is a bound for the graph diameter. Also, the stability of the achieved 1-balanced state is studied. The above results are extended to the case of unbounded diameter, essentially keeping the time bounds, via special averaging of the graph diameter over time. Our algorithms can be considered anytime ones, in the sense that they can be stopped at any time during the execution, since they never make loads negative and never worsen the state as the execution progresses. In addition, we describe a version of our algorithms, where each node may transfer load to and from several neighbors at each round, as a heuristic for better performance. The algorithms are generalized to the asynchronous distributed model. We also introduce a self-stabilizing version of our asynchronous algorithms.

关键词： Load balancing Dynamic graph General graph deterministic algorithm Distributed algorithm Asynchronous system Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATE LEVELS IN LINE ARRANGEMENTS

引用

SIAM JOURNAL ON COMPUTING 1991年第2期20卷 222-227页

作者： MATOUSEK, J CHARLES UNIV DEPT COMP SCI CS-11800 PRAGUE 1 CZECHOSLOVAKIA

An arrangement L of n lines in the plane is considered. A d-approximate level k for L is a polygonal line meeting every vertical exactly once, such that for its every point p there are at least k - d and at most k + d lines of L above p. A d-approximate leveling for L is a collection P1, P2, ..., P[n/2d], where every P(i) is a d-approximate level 2di. A deterministic algorithm is given that, for a given L and a parameter r less-than-or-equal-to n, computes an (n/r)-approximate leveling for L, whose approximate levels consist of O(r2) segments in total. The time complexity of this algorithm is O(nr4/3(log n)4/3(log log n + log r)c) (c a small constant), which is now outperformed by algorithms of Matousek [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 1-10] and Agarwal [Proc. 5th Annual ACM Symposium on Computational Geometry, 1989, pp. 11-21]. A substantially different and elementary method is used here. An approximate leveling can be directly used for approximate halfplanar range counting, but it can also be used for plane partitioning applications, and thus as a subroutine in many recent computational geometry algorithms.

关键词： LINE ARRANGEMENT LEVEL APPROXIMATE LEVEL deterministic algorithm RANGE COUNTING COMPUTATIONAL GEOMETRY

来源：评论

学校读者我要写书评

暂无评论

Byzantine gathering in polynomial time

引用

DISTRIBUTED COMPUTING 2022年第3期35卷 235-263页

作者： Bouchard, Sebastien Dieudonne, Yoann Lamani, Anissa Sorbonne Univ LIP6 CNRS F-75005 Paris France Univ Picardie Jules Verne Lab MIS Amiens France Ecole Int Sci Traitement Informat EISTI Cergy France

Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are integral Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm integral of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in O(log log log n) bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and l with strong teams.

关键词： Gathering deterministic algorithm Mobile agent Byzantine fault Polynomial time

来源：评论

学校读者我要写书评

暂无评论

Modifying the logic gate symbols to enrich the designing of the computer systems by 3-D bit-matrices

引用

AIN SHAMS ENGINEERING JOURNAL 2018年第4期9卷 3207-3216页

作者： Badr, Assem Modern Acad Engn & Technol Cairo Egypt

Recently, the most computer and digital systems are built based on the parallelism to increase their speed of processing. The complications of these systems are increasing proportionally with the complexity of the used parallelism methodologies. According to the growing of this complexity, this research proposes a modification to enhance designing tasks by the concept of the 3-dimensions easily. This research introduces a novel terminology called "Bit-Vector-Matrix". Moreover, this research modifies the standard logic symbols beside reformulates their conventional Boolean algebraic expressions to become more convenient and compatible with the "Bit-Vector-Matrix". We proposed novel logic gate symbols called "Peer-logic-gates". They are useful for representing the intensive concurrent logical operations through intensive parallel digital buses in computer systems. In addition, they will be a promising teaching tool to instruct many computer courses. This paper constructed based on the deterministic algorithm, realized using VHDL codes and evaluated by the reliable simulator "Modelsim". (C) 2018 Ain Shams University.

关键词： Models deterministic algorithm VHDL modules Microprocessors Boolean algebra Matrices

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：