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

Memory optimal distance-2-dispersion with termination

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2025年

作者： Kaur, Tanvir Mondal, Kaushik Indian Inst Technol Ropar Dept Math Rupnagar 140001 Punjab India

The aim of the dispersion problem is to place a set of k(= n, it is guaranteed that the nodes with robots form a maximal independent set of the underlying network. The graph G=(V,E) is a port-labeled graph with n node... 详细信息

The aim of the dispersion problem is to place a set of k(<= n) mobile robots in the nodes of an unknown graph consisting of n nodes such that in the final configuration each node contains at most one robot, starting from any arbitrary initial configuration of the robots on the graph. In this work, we propose a variant of the dispersion problem, namely Distance-2-Dispersion, in short, D-2-D, where we start with any number of robots, and put an additional constraint that no two adjacent nodes contain robots in the final configuration. That is, the distance between any two nodes with robots must be at least 2. However, even if the number of robots k is less than n, it might be the case that it is not possible for each robot to find a distinct node to reside, maintaining our added constraint. More specifically, if a maximal independent set is already formed by the nodes containing a robot each, then any other unsettled robot will not find a node to settle. Hence we allow multiple robots to sit on some nodes only if there is no place to sit. If k >= n, it is guaranteed that the nodes with robots form a maximal independent set of the underlying network. The graph G=(V,E) is a port-labeled graph with n nodes and m edges, where nodes are anonymous. The robots have unique IDs in the range [1,L], where L >= k. Co-located robots can communicate among themselves. We provide an algorithm that solves D-2-D starting from a rooted configuration (i.e. initially all the robots are co-located) and terminates after 2 Delta(8m-3n+3) synchronous rounds using O(log n) memory per robot, without using any global knowledge of the graph parameters m, n and Delta, the maximum degree of the graph. We provide Omega(log n) lower bound on the memory requirement by the robots to solve the D-2-D problem. Thus our algorithm is memory-optimal. We conjecture that the time required by the robots to solve the D-2-D problem, provided each of them have O(log n) memory, is Omega(m Delta) rounds. We further

关键词： Mobile robots dispersion distance-2-dispersion deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

deterministic algorithmS FOR THE HIDDEN SUBGROUP PROBLEM

引用

QUANTUM INFORMATION & COMPUTATION 2022年第9-10期22卷 755-769页

作者： Nayak, Ashwin Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp 200 Univ Ave West Waterloo ON N2L 3G1 Canada

We present deterministic algorithms for the Hidden Subgroup Problem. The first algorithm, for abelian groups, achieves the same asymptotic worst-case query complexity as the optimal randomized algorithm, namely O(root n), where n is the order of the group. The analogous algorithm for non-abelian groups comes within a root log n factor of the optimal randomized query complexity. The best known randomized algorithm for the Hidden Subgroup Problem has expected query complexity that is sensitive to the input, namely O(root n/m), where m is the order of the hidden subgroup. In the first version of this article [1, Sec. 5], we asked if there is a deterministic algorithm whose query complexity has a similar dependence on the order of the hidden subgroup. Prompted by this question, Ye and Li [2] present deterministic algorithms for abelian groups which solve the problemwith O (root n/m) queries, and find the hidden subgroup with O(root n (logm)/m + logm) queries. Moreover, they exhibit instances which show that in general, the deterministic query complexity of the problem may be o(p n/m), and that of finding the entire subgroup may also be o(root n/m) or even omega(root n/m). We present a different deterministic algorithm for the Hidden Subgroup Problem that also has query complexity O(root n/m) for abelian groups. The algorithm is arguably simpler. Moreover, it works for non-abelian groups, and has query complexity O(p (n/ m) log(n/m)) for a large class of instances, such as those over supersolvable groups. We build on this to design deterministic algorithms to find the hidden subgroup for all abelian and some nonabelian instances, at the cost of a logm multiplicative factor increase in the query complexity.

关键词： Hidden Subgroup Problem deterministic algorithm query complexity abelian group non-abelian group generating pair bicrossed product

来源：评论

学校读者我要写书评

暂无评论

SLASH: A deterministic block placement algorithm based on Sequence-Pair

SLASH: A deterministic block placement algorithm based on Se...

引用

IEEE Asia-Pacific Conference on Circuits and Systems (APCCAS-2000)

作者： Takashima, Y Murata, H JAIST Hokuriku Ishikawa Japan

ISBN: (纸本)0780362535

This paper proposes a deterministic algorithm for block placement problem, based on Sequence-Pair (SP), unlike most of the previous approaches use simulated annealing (SA). An initial placement is obtained by a simple analytical method and an SP is extracted from the placement. Then the algorithm moves modules conceptually in +45 degree direction, and in -45 degree direction, alternately until the evaluation converges, utilizing the SP. Our experiments show the algorithm runs 100 times faster than SA, while keeping the same level of area and total wire length performance.

关键词： Sequence-Pair block placement deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

deterministic algorithms for the hidden subgroup problem

引用

INFORMATION AND COMPUTATION 2022年第PartA期289卷

作者： Ye, Zekun Li, Lvzhou Sun Yat Sen Univ Inst Quantum Comp & Comp Theory Sch Comp Sci & Engn Guangzhou 510006 Peoples R China Sun Yat Sen Univ Minist Educ Key Lab Machine Intelligence & Adv Comp Guangzhou 510006 Peoples R China Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510006 Peoples R China

The hidden subgroup problem (HSP) plays a crucial role in the field of quantum computing, since several celebrated quantum algorithms including Shor's algorithm have a uniform description in the framework of HSP. The problem is as follows: for a finite group G and a finite set X, given a function f : G -> X and the promise that for any g(1), g(2) is an element of G, f (g(1)) = f (g(2)) iff g(1)H = g(2)H for a subgroup H <= G, the goal of the decision version is to determine whether H is trivial, and the goal of the search version is to find H. Nayak (2021) asked whether there exist deterministic algorithms with O root vertical bar G vertical bar/vertical bar H vertical bar) query complexity for HSP. We answer this problem for Abelian groups, which also extends the main results of Ye et al. (2021), since here the algorithms do not rely on any prior knowledge of H. (c) 2022 Elsevier Inc. All rights reserved.

关键词： Quantum computing Hidden subgroup problem Query complexity deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

SLASH:A deterministic Block Placement algorithm Based on Sequence-Pair

SLASH:A Deterministic Block Placement Algorithm Based on Seq...

引用

Electronic Communication Systems--The 2000 IEEE Asia-Pacific Conference on Circuits and Systems

作者： Yasuhiro Takashima Hiroshi Murata JAIST IshikawaJapan

This paper proposes a deterministic algorithm for block placement problem,based on Sequence-Pair(SP),unlike most of the previous approaches use simulated annealing (SA).An initial placement is obtained by a simple analytical method and an SP is extracted from the *** the algorithm moves modules conceptually in +45 degree direction,and in -45 degree direction,alternately until the evaluation converges, utilizing the *** experiments show the algorithm runs 100 times faster than SA,while keeping the same level of area and total wire length performance.

关键词： Sequence-Pair block placement deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

deterministic Approximate Methods for Maximum Consensus Robust Fitting

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2021年第3期43卷 842-857页

作者： Le, Huu Chin, Tat-Jun Eriksson, Anders Do, Thanh-Toan Suter, David Chalmers Univ Technol S-41296 Gothenburg Sweden Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Univ Queensland Sch Informat Technol & Elect Engn Brisbane Qld 4072 Australia Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Edith Cowan Univ Sch Sci Joondalup WA 6027 Australia

Maximum consensus estimation plays a critically important role in several robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals. Matlab code and demo program for our methods can be downloaded from https://***/FQcxpi.

关键词： Approximation algorithms Optimization Computer vision Mathematical model Estimation Computational modeling Data models Maximum consensus robust fitting deterministic algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Normal projection： deterministic and probabilistic algorithms

引用

Frontiers of Mathematics in China 2014年第1期9卷 93-99页

作者： Dongmei LI Jinwang LIU Weijun LIU Department of Mathematics and Computing Sciences Hunan University of Scienceand Technology Xiangtan 411201 China Department of Mathematics and Statistics Central South University Changsha 410083 China

We consider the following problem： for a collection of points in an n-dimensional space, find a linear projection mapping the points to the ground field such that different points are mapped to different values. Such projections are called normal and are useful for making algebraic varieties into normal positions. The points may be given explicitly or implicitly and the coefficients of the projection come from a subset S of the ground field. If the subset S is small, this problem may be hard. This paper deals with relatively large S, a deterministic algorithm is given when the points are given explicitly, and a lower bound for success probability is given for a probabilistic algorithm from in the literature.

关键词： Normal projection primary decomposition of ideal deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Time versus cost tradeoffs for deterministic rendezvous in networks

引用

DISTRIBUTED COMPUTING 2016年第1期29卷 51-64页

作者： Miller, Avery Pelc, Andrzej Univ Quebec Outaouais Gatineau PQ Canada

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. Each agent has a distinct integer label from the set {1,..., L}. Two main efficiency measures of rendezvous are its time (the number of rounds until the meeting) and its cost (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (where E and a corresponding exploration procedure are known to both agents) and of the size L of the label space. We present two natural rendezvous algorithms. algorithm Cheap has cost O (E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O (EL). algorithm Fast has both time and cost O (E log L). Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically E (i.e., of cost E + o(E)) must have time Omega (EL). On the other hand, we show that any deterministic rendezvous algorithm with time complexity O (E log L) must have cost Omega (E log L).

关键词： Rendezvous deterministic algorithm Mobile agent Cost Time

来源：评论

学校读者我要写书评

暂无评论

deterministic root finding over finite fields using Graeffe transforms

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2016年第3期27卷 237-257页

作者： Grenet, Bruno van der Hoeven, Joris Lecerf, Gregoire Univ Montpellier UMR CNRS 5506 LIRMM CC477 161 Rue Ada F-34095 Montpellier 5 France Lab Informat Ecole Polytech LIX UMR CNRS 7161 Campus Ecole Polytech F-91120 Palaiseau France

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field . Our algorithms were designed to be particularly efficient in the case when the cardinality of the multiplicative group of is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.

关键词： Polynomial root finding Finite field Graeffe transform deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

A deterministic Attitude Estimation Using a Single Vector Information and Rate Gyros

引用

IEEE-ASME TRANSACTIONS ON MECHATRONICS 2015年第5期20卷 2630-2636页

作者： Vinod, Abraham P. Mahindrakar, Arun D. Bandyopadhyay, Sandipan Muralidharan, Vijay Indian Inst Technol Dept Elect Engn Madras 600036 Tamil Nadu India Indian Inst Technol Dept Engn Design Madras 600036 Tamil Nadu India

This paper proposes a deterministic estimator for the estimation of the attitude of a rigid body. A deterministic estimator uses a minimal set of information and does not try to minimize a cost function or fit the measurements into a stochastic process. The proposed estimator obtains the attitude estimation utilizing only the properties of the rotational group SO(3). The information set required by the proposed estimator is a single vector information and rate gyro readings. For systems in which one of the rotational freedom is constrained, the proposed estimator provides an accurate estimate of the reduced attitude. The performance of the algorithm is verified on different experimental testbeds.

关键词： Attitude estimation deterministic algorithm inertial measurement unit special orthogonal group

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：