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

21st International Conference on Distributed Computing and Intelligent Technology

作者： Pandit, Himani Pandit, Supantha Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

ISBN: (纸本)9783031814037;9783031814044

In the dispersion problem, a group of k <= n mobile robots, initially placed on the vertices of an anonymous graph G with n vertices, must redistribute themselves so that each vertex hosts no more than one robot. We address this challenge on an anonymous triangular grid graph, where each vertex can connect to up to six adjacent vertices. We propose a distributed deterministic algorithm that achieves dispersion on an unoriented triangular grid graph in O(root n) time, where n is the number of vertices. Each robot requires O(log n) bits of memory. The time complexity of our algorithm and the memory usage per robot are optimal. This work builds on previous studies by Kshemkalyani et al. [WALCOM 2020 [17]] and Banerjee et al. [ALGOWIN 2024 [3]]. Importantly, our algorithm terminates without requiring prior knowledge of n and resolves a question posed by Banerjee et al. [ALGOWIN 2024 [3]].

关键词： Distributed algorithms Mobile robots Dispersion Triangular grid deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

引用

INFORMATION AND COMPUTATION 2015年 243卷 86-111页

作者： Bodlaender, Hans L. Cygan, Marek Kratsch, Stefan Nederlof, Jesper Univ Utrecht NL-3508 TC Utrecht Netherlands Univ Warsaw Inst Informat PL-00325 Warsaw Poland

It is well known that many local graph problems, like VERTEX COVER and DOMINATING SET, can be solved in time 2(O(tw))|V|(O(1)) for graphs G =(V, E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw(O(tw))|V|(O(1)). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time c(tw)|V|(O(1)) for a small constant c, e.g., for HAMILTONIAN CYCLE and STEINER TREE. Naturally, this raises the question whether randomization is necessary to achieve this runtime;furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c(tw)|V|(O(1)) time algorithms, also for weighted and counting versions. For example, in this time we can solve TRAVELING SALESMAN or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions;we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems;we show how to evaluate those formulas via dynamic programming. (C) 2014 Elsevier Inc. All rights reserved.

关键词： deterministic algorithms GRAPH theory PROBLEM solving TREE graphs DECOMPOSITION method (Mathematics) GRAPH connectivity PATHS & cycles (Graph theory)

来源：评论

学校读者我要写书评

暂无评论

deterministic polynomial-time algorithms for designing short DNA words

引用

THEORETICAL COMPUTER SCIENCE 2013年 494卷 144-160页

作者： Kao, Ming-Yang Leung, Henry C. M. Sun, He Zhang, Yong Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Max Planck Inst Informat Leipzig Germany Fudan Univ Inst Modem Math & Phys Shanghai Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Beijing 100864 Peoples R China

Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9 . max{log n, k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1 log n + 6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al.. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. (c) 2013 Elsevier B.V. All rights reserved.

关键词： DNA word design deterministic algorithms Derandomization

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Size-Constrained Non-Monotone Submodular Maximization in deterministic Linear Time 23

Approximation Algorithms for Size-Constrained Non-Monotone S...

引用

29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)

作者： Chen, Yixin Kuhnle, Alan Texas A&M Univ College Stn TX 77843 USA

ISBN: (纸本)9798400701030

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + epsilon which is the first linear-time streaming algorithm;a simpler deterministic linear-time algorithm with a ratio of 11.657;and a (4 + O (epsilon))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + epsilon in O-epsilon (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.

关键词： Submodular Maximization deterministic algorithms Linear Time

来源：评论

学校读者我要写书评

暂无评论

Simulation of average fading duration using deterministic method

引用

ELECTRONICS LETTERS 1999年第7期35卷 542-544页

作者： Xiao, W Dubey, VK Ong, JT Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

Measurements and modelling of average fading duration (AFD) for a mobile channel with line-of-sight (LOS) component at VHF Frequencies (69.75 MHz) show that the deterministic method can be used to simulate the AFD of a mobile channel, and that a mobile channel with a LOS component can be modelled using Loo's model. To obtain an accurate simulated AFD, an appropriate sample interval should be used in the simulation.

关键词： Loo model mobile channel mobile radio Mobile radio systems VHF frequencies digital simulation Radiowave propagation 69.75 MHz deterministic algorithms line-of-sight component VHF radio propagation deterministic method Statistics average fading duration simulation telecommunication computing sample interval Other topics in statistics fading channels LOS component modelling Communications computing statistical analysis

来源：评论

学校读者我要写书评

暂无评论

Complexity of solving nonlinear equations in the deterministic, randomized and quantum settings

引用

APPLIED MATHEMATICS AND COMPUTATION 2013年 224卷 652-662页

作者： Gocwin, Maciej Kacewicz, Boleslaw AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland

We consider the root finding of a real-valued function f defined on the d-dimensional unit cube. We assume that f has r continuous partial derivatives, with all partial derivatives of order r being Holder functions with the exponent rho. We study the epsilon-complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic epsilon-complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized epsilon-complexity is of order epsilon(-d/(r+rho)). In the quantum setting, the epsilon-complexity is shown to be of order epsilon(-d/(2(r+rho))). This means that a quadratic speed-up is achieved on a quantum computer. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Nonlinear equations deterministic algorithms Randomized algorithms Quantum algorithms Optimality Complexity

来源：评论

学校读者我要写书评

暂无评论

Improved lower bound for deterministic broadcasting in radio networks

引用

THEORETICAL COMPUTER SCIENCE 2011年第29期412卷 3568-3578页

作者： Brito, Carlos Fisch Vaya, Shailesh Indian Inst Technol Patna Dept Comp Sci & Engn Patna 800013 Bihar India Univ Fed Ceara Dept Computacao Fortaleza Ceara Brazil

We consider the problem of deterministic broadcasting in radio networks when the nodes have limited knowledge about the topology of the network. We show that for every deterministic broadcasting protocol there exists a network, of radius 2, for which the protocol takes at least Omega(n(1/2)) rounds for completing the broadcast. Our argument can be extended to prove a lower bound of Omega((nD)(1/2)) rounds for broadcasting in radio networks of radius D. This resolves one of the open problems posed in Kowalski and Pelc (2004) [24], where the authors proved a lower bound of Omega(n(1/4)) rounds for broadcasting in constant diameter networks. We prove the new lower bound for a special family of radius 2 networks. Each network of this family consists of 0(root n) components which are connected to each other via only the source node. At the heart of the proof is a novel simulation argument, which essentially says that any arbitrarily complicated strategy of the source node can be simulated by the nodes of the networks, if the source node just transmits partial topological knowledge about some component instead of arbitrary complicated messages. To the best of our knowledge this type of simulation argument is novel and may be useful in further improving the lower bound or may find use in other applications. (C) 2011 Elsevier B.V. All rights reserved.

关键词： deterministic algorithms Broadcast Radio networks Limited topological knowledge Lower Bound Simulations Selective families

来源：评论

学校读者我要写书评

暂无评论

deterministic Sparse Suffix Sorting in the Restore Model

引用

ACM TRANSACTIONS ON algorithms 2020年第4期16卷 1–53页

作者： Fischer, Johannes Tomohiro, I Koppl, Dominik TU Dortmund Dept Comp Sci Otto Hahn Str 14 D-44221 Dortmund Germany Kyushu Inst Technol Kawazu 680-4 Iizuka Fukuoka 8208502 Japan Kyushu Univ Dept Comp Sci 744 Motooka Fukuoka 8190395 Japan

Given a text T of length n, we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O(c root lg n + m lg m lg n lg* n) time with O(m) words of space under the premise that the space of T is rewritable, where m <= n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m <= c <= n that must be compared for distinguishing the designated suffixes.

关键词： Sparse suffix sorting online algorithms deterministic algorithms alphabet reduction edit-sensitive parsing

来源：评论

学校读者我要写书评

暂无评论

deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples

引用

EVOLUTIONARY COMPUTATION 2016年第2期24卷 319-346页

作者： Hu, Xiao-Bing Wang, Ming Leeson, Mark S. Di Paolo, Ezequiel A. Liu, Hao Beijing Normal Univ State Key Lab Earth Surface Proc & Resource Ecol Beijing 100875 Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL W Midlands England Univ Basque Country Ikerbasque Basque Sci Fdn Ctr Res Life Mind & Soc San Sebastian 20080 Spain Beijing Metropolitan Traff Informat Ctr Beijing 100161 Peoples R China

Inspirations from nature have contributed fundamentally to the development of evolutionary computation. Learning from the natural ripple-spreading phenomenon, this article proposes a novel ripple-spreading algorithm (RSA) for the path optimization problem (POP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source is the first to be reached. This very simple principle forms the foundation of the proposed RSA. In contrast to most deterministic top-down centralized path optimization methods, such as Dijkstra's algorithm, the RSA is a bottom-up decentralized agent-based simulation model. Moreover, it is distinguished from other agent-based algorithms, such as genetic algorithms and ant colony optimization, by being a deterministic method that can always guarantee the global optimal solution with very good scalability. Here, the RSA is specifically applied to four different POPs. The comparative simulation results illustrate the advantages of the RSA in terms of effectiveness and efficiency. Thanks to the agent-based and deterministic features, the RSA opens new opportunities to attack some problems, such as calculating the exact complete Pareto front in multiobjective optimization and determining the kth shortest project time in project management, which are very difficult, if not impossible, for existing methods to resolve. The ripple-spreading optimization principle and the new distinguishing features and capacities of the RSA enrich the theoretical foundations of evolutionary computation.

关键词： Agent-based model deterministic algorithms ripple-spreading algorithm path optimization

来源：评论

学校读者我要写书评

暂无评论

deterministic System Identification Using RBF Networks

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2014年第1期2014卷 1-10页

作者： de Almeida Rego, Joilson Batista Martins, Allan de Medeiros Costa, Evandro de B. Univ Fed Rio Grande do Norte LACI DEE Postgrad Program Elect & Comp Engn PPgEEC BR-59078970 Natal RN Brazil Fed Univ Alagoas UFAL Inst Comp Sci BR-57072900 Maceio AL Brazil Univ Fed Rio Grande do Norte Dept Elect Engn BR-59078970 Natal RN Brazil

This paper presents an artificial intelligence application using a nonconventional mathematical tool: the radial basis function (RBF) networks, aiming to identify the current plant of an induction motor or other nonlinear systems. Here, the objective is to present the RBF response to different nonlinear systems and analyze the obtained results. A RBF network is trained and simulated in order to obtain the dynamical solution with basin of attraction and equilibrium point for known and unknown system and establish a relationship between these dynamical systems and the RBF response. On the basis of several examples, the results indicating the effectiveness of this approach are demonstrated.

关键词： SYSTEM identification deterministic algorithms RADIAL basis functions NONLINEAR systems DYNAMICAL systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：