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

deterministic protocols in the SINR model without knowledge of coordinates

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 115卷 121-145页

作者： Moses, William K., Jr. Vaya, Shailesh Indian Inst Technol Madras Dept Comp Sci & Engn Chennai 600036 Tamil Nadu India Xerox Res Ctr India Bangalore 560048 Karnataka India Technion Israel Inst Technol Fac Ind Engn & Management Haifa Israel

This work studies multi-broadcasting for the SINR (Signal-to-Interference-plus-Noise-Ratio) model, assuming a subset of nodes are initially awake, when each device only has access to knowledge about the total number of nodes in the network ti, the range from which each node's label is taken {1, ..., N}, and the label of the device itself. We assume no knowledge of the physical coordinates of devices and no knowledge of the neighborhood of each node. We present a deterministic protocol for this problem that runs in O(n lg N lgn) rounds. There is no known polytime deterministic algorithm for this setting. A lower bound of Omega(n lg N) rounds is known for deterministic broadcasting without local knowledge [30]. We also present algorithms to achieve multi-broadcast in O(n lgN) rounds and create a backbone in O(n lgN) rounds, assuming that all nodes are initially awake. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Distributed algorithms Multi-broadcast Non-spontaneous wakeup Backbone creation Signal-to-Interference-plus-Noise-Ratio model Wireless networks deterministic algorithms Strongly selective family based dilution

来源：评论

学校读者我要写书评

暂无评论

Pebble Guided Treasure Hunt in Plane 11th

Pebble Guided Treasure Hunt in Plane

引用

11th International Conference on Networked Systems (NETYS)

作者： Bhattacharya, Adri Gorain, Barun Mandal, Partha Sarathi Indian Inst Technol Guwahati Gauhati India Indian Inst Technol Bhilai Bhilai India

ISBN: (纸本)9783031377648;9783031377655

We study the problem of treasure hunt in a Euclidean plane by a mobile agent with the guidance of pebbles. The initial position of the agent and position of the treasure are modeled as special points in the Euclidean plane. The treasure is situated at a distance at most D > 0 from the initial position of the agent. The agent has a perfect compass, but an adversary controls the speed of the agent. Hence, the agent can not measure how much distance it traveled for a given time. The agent can find the treasure only when it reaches the exact position of the treasure. The cost of the treasure hunt is defined as the total distance traveled by the agent before it finds the treasure. The agent has no prior knowledge of the position of the treasure or the value of D. An Oracle, which knows the treasure's position and the agent's initial location, places some pebbles to guide the agent towards the treasure. Once decided to move along some specified angular direction, the agent can decide to change its direction only when it encounters a pebble or a special point. We ask the following central question in this paper: "For given k >= 0, what is cheapest treasure hunt algorithm if at most k pebbles are placed by the Oracle?" We show that for k = 1, there does not exist any treasure hunt algorithm that finds the treasure with finite cost. We show the existence of an algorithm with cost O(D) for k = 2. For k > 8 we have designed an algorithm that uses k many pebbles to find the treasure with cost O(k(2))+ D(sin theta' + cos theta'), where theta' = pi/2(k-8). The second result shows the existence of an algorithm with cost arbitrarily close to D for sufficiently large values of D.

关键词： Treasure Hunt Mobile agent Pebbles Euclidean plane deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

A survey on cloud computing scheduling algorithms

引用

MULTIAGENT AND GRID SYSTEMS 2022年第2期18卷 119-148页

作者： Malekimajd, Marzieh Safarpoor-Dehkordi, Ali Iran Univ Sci & Technol Sch Comp Engn Tehran Iran Iran Univ Sci & Technol Tehran Iran

Cloud computing has emerged as one of the hottest topics in technology and has quickly become a widely used information and communication technology model. Performance is a critical component in the cloud environment concerning constraints like economic, time, and hardware issues. Various characteristics and conditions for providing solutions and designing strategies must be dealt with in different situations to perform better. For example, task scheduling and resource allocation are significant challenges in cloud management. Adopting proper techniques in such conditions leads to performance improvement. This paper surveys existing scheduling algorithms concerning the macro design idea. We classify these algorithms into four main categories: deterministic algorithms, metaheuristic algorithms, learning algorithms, and algorithms based on game theory. Each category is discussed by citing appropriate studies, and the MapReduce review is addressed as an example.

关键词： Cloud computing scheduling deterministic algorithms optimization algorithms metaheuristic algorithms learning algorithms

来源：评论

学校读者我要写书评

暂无评论

A deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique 2021

A Deterministic Algorithm for the MST Problem in Constant Ro...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Nowicki, Krzysztof Univ Copenhagen Copenhagen Denmark Univ Wroclaw Wroclaw Poland

ISBN: (纸本)9781450380539

In this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model. In the Congested Clique model there are n players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange O(log n) bit messages. The studies of this model began with the MST problem: in the paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05] that defines the Congested Clique model the authors give a deterministic O(log log n) round algorithm that improved over a trivial O(log n) round adaptation of Boravka's algorithm. There was a sequence of gradual improvements to this result: an O(log log log n) round algorithm by Hegeman, Pandurangan, Pemmaraju, Sardeshmukh, and Scquizzato [PODC'15], an O(log* n) round algorithm by Ghaffari and Parter, [PODC'16] and an O(1) round algorithm by Jurdzinski and Nowicki, [SODA'18], but all those algorithms were randomized. Therefore, the question about the existence of any deterministic o(log log n) round algorithms for the Minimum Spanning Tree problem remains open since the seminal paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05]. Our result resolves this question and establishes that O(1) rounds is enough to solve the MST problem in the Congested CI iq ue model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to a variant of the M PC model using machines with local memory of size O(n).

关键词： Minimum Spanning Tree MST deterministic algorithms Graph algorithms Distributed algorithms Congested Clique Parallel algorithms Massively Parallel algorithms MapReduce

来源：评论

学校读者我要写书评

暂无评论

deterministic Mincut in Almost-Linear Time 2021

Deterministic Mincut in Almost-Linear Time

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Li, Jason Carnegie Mellon Univ Pittsburgh PA 15213 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450380539

We present a deterministic (global) mincut algorithm for weighted, undirected graphs that runs in m(1)(+o(1)) time, answering an open question of Karger from the 1990s. To obtain our result, we derandomize the construction of the skeleton graph in Karger's near-linear time mincut algorithm, which is its only randomized component. In particular, we partially de-randomize the well-known Benczur-Karger graph sparsification technique by random sampling, which we accomplish by the method of pessimistic estimators. Our main technical component is designing an efficient pessimistic estimator to capture the cuts of a graph, which involves harnessing the expander decomposition framework introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications.

关键词： minimum cut deterministic algorithms de-randomization graph sparsification

来源：评论

学校读者我要写书评

暂无评论

Treasure Hunt in Graph Using Pebbles 24th

Treasure Hunt in Graph Using Pebbles

引用

24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)

作者： Bhattacharya, Adri Gorain, Barun Mandal, Partha Sarathi Indian Inst Technol Guwahati Gauhati 781039 India Indian Inst Technol Bhilai Bhilai India

ISBN: (纸本)9783031210167;9783031210174

In this paper, we study the treasure hunt problem in a graph by a mobile agent. The nodes in the graph G = (V, E) are anonymous and the edges incident to a vertex v is an element of V whose degree is deg(v) and they are labeled arbitrarily as 0, 1, ..., deg(v) - 1. At a node t in G a stationary object, called treasure is located. The mobile agent that is initially located at a node s in G, the starting point of the agent, must find the treasure by reaching the node t. The distance from s to t is D. The time required to find the treasure is the total number of edges the agent visits before it finds the treasure. The agent neither have any prior knowledge about the graph nor the position of the treasure. An oracle that knows the graph, the agent's initial position, and the position of the treasure, places some pebbles on the nodes, at most one per node, of the graph to guide the agent towards the treasure. This paper aims to study the trade-off between the number of pebbles provided and the time required to find the treasure. To be specific, we aim to answer the following question: - "What is the minimum time for treasure hunt in a graph with maximum degree Delta and diameter D if k pebbles are placed?" We answer the above question when k < D and k = cD for some positive integer c. We design efficient algorithms for the agent for different values of k. We also propose an almost matching lower bound result for k < D.

关键词： Treasure hunt Mobile agent Anonymous graph Pebbles deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Hybridized classification algorithms for data classification applications: A review

引用

EGYPTIAN INFORMATICS JOURNAL 2021年第2期22卷 185-192页

作者： Sherwani, F. Ibrahim, B. S. K. K. Asad, Muhammad Mujtaba FAST Natl Univ Comp & Emerging Sci Dept Comp Sci Karachi Sindh Pakistan Coventry Univ Fac Engn Environm & Comp Sch Mech Aerosp & Automot Priory St Coventry CV1 5FB W Midlands England Sukkur IBA Univ Dept Educ Airport Rd Sukkur Sindh Pakistan

Machine-based classification usually involves some computer programs, known as algorithms, developed using several mathematical formulations to accelerate the automated classification process. Along with the exponential increase in the size and computational complexity of the data today, such optimized, robust, agile and reliable computational algorithms are required which can efficiently carry out these conforming classification tasks. In this review paper, deterministic optimization techniques have been analysed that are efficiently employed for machine learning applications. In this review, systematic literature review approach has been adopted in which 200 research articles were downloaded from which 100 latest articles has been selected based on the most commonly employed neural networks' techniques. Moreover, the reported neural networks techniques based on Back Propagation Neural Network (BPNN), Recurrent Neural Networks (RNNs) Algorithm and Levenberg-Marquardt (LM) with several hybridized classification algorithms based on optimization techniques have been indicated that are commonly used to optimize and benefit the classification process. (C) 2021 THE AUTHORS. Published by Elsevier BV on behalf of Faculty of Computers and Artificial Intelligence, Cairo University.

关键词： Recurrent Neural Networks (RNNs) algorithm Back Propagation Neural Network (BPNN) deterministic algorithms Machine learning Levenberg-Marquardt (LM)

来源：评论

学校读者我要写书评

暂无评论

Artificial Neural Networks Generated by Low Discrepancy Sequences 14th

Artificial Neural Networks Generated by Low Discrepancy Sequ...

引用

14th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC)

作者： Keller, Alexander Van Keirsbilck, Matthijs NVIDIA Fasanenstr 81 D-10623 Berlin Germany

ISBN: (纸本)9783030983192;9783030983185

Artificial neural networks can be represented by paths. Generated as random walks on a dense network graph, we find that the resulting sparse networks allow for deterministic initialization and even weights with fixed sign. Such networks can be trained sparse from scratch, avoiding the expensive procedure of training a dense network and compressing it afterwards. Although sparse, weights are accessed as contiguous blocks of memory. In addition, enumerating the paths using deterministic low discrepancy sequences, for example variants of the Sobol' sequence, amounts to connecting the layers of neural units by progressive permutations, which naturally avoids bank conflicts in parallel computer hardware. We demonstrate that the artificial neural networks generated by low discrepancy sequences can achieve an accuracy within reach of their dense counterparts at a much lower computational complexity.

关键词： Neural networks Low discrepancy sequences Sparsity deterministic algorithms Parallel computer hardware

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Adaptive stochastic and hybrid nonlinear optimization algorithms for improving the effectiveness of the biological processes at WWTP

引用

BIOCHEMICAL ENGINEERING JOURNAL 2023年第1期193卷

作者： Piotrowski, Robert Milewski, Krzysztof Maciag, Bartosz Gdansk Univ Technol Fac Elect & Control Engn EkoTech Ctr G Narutowicza 11-12 PL-80233 Gdansk Poland

Wastewater treatment plays an important factor in the modern world. Insufficient treatment may result in environmental pollution which can further lead to disasters and diseases. However, processes that take place inside wastewater treatment plants (WWTP) are highly complex in nature, therefore it is difficult to design an efficient, optimal control system. The problem regarding biochemical reactions inside Sequential Batch Reactor (SBR) is analyzed in this paper and the optimization problem is defined. Next, chosen optimization methods including both deterministic and metaheuristic algorithms are carefully described. Series of simulation experi-ments are conducted based on a verified model of SBR from Swarzewo Wastewater Treatment Plant (WWTP) -Northern Poland. The proposed optimal control system allowed to increase the efficiency, improve the quality of outflow (reduction of Chemical Oxygen Demand (COD), total nitrogen (Ntot) and total phosphorus (Ptot)) and reduce wastewater treatment costs.

关键词： Adaptive optimization Biological processes deterministic algorithms Hybrid optimization Metaheuristic algorithms Mixed integer optimization Nonlinear optimization Optimal control Wastewater treatment plant SBR

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：