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

deterministic (1/2+e)-APPROXIMATION FOR SUBMODULAR MAXIMIZATION OVER A MATROID

SIAM JOURNAL ON COMPUTING 2023年第4期52卷 945-967页

作者： Buchbinder, Niv Feldman, Moran Garg, Mohit Tel Aviv Univ Stat & Operat Res Dept Tel Aviv Israel Open Univ Israel Dept Math & Comp Sci Raanana Israel Univ Haifa Dept Psychol Haifa Israel Indian Inst Sci Dept Comp Sci & Automat Bengaluru India

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2+e)-approximation for the problem (for some \varepsilon \geq 8 \cdot 10 -4). This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey, and Fisher in 1978.

关键词： submodular optimization matroid deterministic algorithms

来源：评论

学校读者我要写书评

暂无评论

Using the method of artificial immune systems to seek the suboptimal program control of deterministic systems

引用

AUTOMATION AND REMOTE CONTROL 2014年第11期75卷 1922-1935页

作者： Panteleev, A. V. Metlitskaya, D. V. Moscow State Aviat Inst Moscow Russia

Determination of the suboptimal programmed control for the continuous deterministic systems by the use of the method of artificial immune systems for search of the conditional global extremum was proposed. An algorithm to solve it which underlies the corresponding software was generated, and a modification of the method was suggested to enhance its efficiency. Examples of solutions of the model problems were given, and the method of artificial immune systems was compared with its modification, as well as with other metaheuristic methods.

关键词： IMMUNE system METAHEURISTIC algorithms deterministic algorithms COMPUTER software IMMUNOLOGY

来源：评论

学校读者我要写书评

暂无评论

deterministic genericity for polynomial ideals

引用

JOURNAL OF SYMBOLIC COMPUTATION 2018年 86卷 20-50页

作者： Hashemi, Amir Schweinfurter, Michael Seiler, Werner M. Isfahan Univ Technol Dept Math Sci Esfahan *** Iran Inst Res Fundamental Sci IPM Sch Math POB 19395-5746 Tehran Iran Univ Kassel Inst Math D-34132 Kassel Germany

We consider several notions of genericity appearing in algebraic geometry and commutative algebra. Special emphasis is put on various stability notions which are defined in a combinatorial manner and for which a number of equivalent algebraic characterisations are provided. It is shown that in characteristic zero the corresponding generic positions can be obtained with a simple deterministic algorithm. In positive characteristic, only adapted stable positions are reachable except for quasi-stability which is obtainable in any characteristic. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Polynomial ideals deterministic algorithms Grobner bases Pommaret bases Generic positions Generic initial ideals Strongly stable ideals Stable ideals Quasi stable ideals Componentwise stability beta-maximal position Noether position

来源：评论

学校读者我要写书评

暂无评论

A synod based deterministic and indulgent leader election protocol for asynchronous large groups

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2022年第2期37卷 220-247页

作者： Srinivasan, Sathyanarayanan Kandukoori, Ramesh Natl Inst Technol Warangal Warangal Telangana India

This paper presents a deterministic and indulgent algorithm for leader election. Our algorithm is adapted to large-scale systems with the primary objective of faster execution time to elect a leader. We modify the singledecree Paxos consensus (Synod) algorithm such that proposers proposing the same value do not conflict with each other. Although any process in the system can initiate election, we restrict the decision making on electing the leader to a select set of processes A, called acceptors. For a given k (= vertical bar A vertical bar) acceptors in the system, our algorithm can tolerate up to f = inverted right perpendiculark/2 - 1inverted left perpendicular failures in A, and any number of process failures outside A. The restriction on decision making allows our algorithm to scale without compromising on performance. Experimental results show that our algorithm is faster to elect a leader than existing algorithms which are optimised for largescale systems. We also adapt our algorithm for leader election in Wireless Sensor Networks (WSNs) and Internet of Things (IoTs) and show that it performs better than the existing graph-based techniques employed in these systems. [GRAPHICS] .

关键词： Leader election deterministic algorithms indulgent algorithms synod Paxos wireless sensor networks and internet of things

来源：评论

学校读者我要写书评

暂无评论

deterministic Replacement Path Covering

引用

ACM TRANSACTIONS ON algorithms 2024年第4期20卷 1-35页

作者： Karthik, C. S. Parter, Merav Tel Aviv Univ Tel Aviv Israel Weizmann Inst Sci Rehovot Israel

In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\subseteq E(G)\) , a replacement path \(P(s,t,F)\) is an \(s\) - \(t\) shortest path in \(G\setminus F\) . For integer parameters \(L,f\) , a replacement path covering ( \(\mathsf{RPC}\) ) is a collection of subgraphs of \(G\) , denoted by \(\mathcal{G}_{L,f}=\{G_deterministic,\ldots,G_{r}\}\) , such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\) ) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\) . The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\) .In the randomized setting, it is easy to build an \((L,f)\) - \(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\) , but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following:—There exist efficient deterministic constructions of \((L,f)\) - \(\mathsf{RPC}\) s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes.—For every \(L,f\) , and \(n\) , there exists

关键词： Fault-tolerant graph algorithms deterministic algorithms distance sensitivity oracles spanners

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

deterministic improved round-trip spanners

引用

INFORMATION PROCESSING LETTERS 2018年 129卷 57-60页

作者： Zhu, Chun Jiang Lam, Kam-Yiu Wisers Informat Ltd Res Dept Hong Kong Hong Kong Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

In this paper, we study the deterministic construction of round-trip spanners for weighted directed graphs. We propose a deterministic algorithm which constructs, for any n-vertex graph G(V, E), a round-trip spanner H(V, E' subset of E) of stretch 2k + epsilon and size O ((k/epsilon) . n(1+1/k) log(nw)), where w is the maximum edge weight of G. Notably, this is the first deterministic construction of round-trip spanners and its stretch-size trade-off even improves the previous state-of-the-art randomized algorithm by Roditty et al. More specifically, the size is asymptotically reduced by a factor of k while the stretch factor remains the same. The result is the first clear improvement on round-trip spanners after about ten years and re-raises the open question that how best we can hope for the stretch size trade-off of round-trip spanners in digraphs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Graph spanners Round-trip spanners deterministic algorithms Shortest distances

来源：评论

学校读者我要写书评

暂无评论

Stochastic versus deterministic models in the analysis of communication systems

引用

IEEE ANTENNAS AND PROPAGATION MAGAZINE 2002年第4期44卷 40-50页

作者： Sarkar, TK Schwarzlander, H Choi, S Palma, MS Wicks, MC Syracuse Univ Dept Comp Sci & Elect Engn Syracuse NY 13244 USA Hanyang Univ Sch Elect & Comp Engn Seoul 133791 South Korea Univ Politecn Madrid ETSI Telecomunicac Dpto Senales Sistemas & Radiocomunicac Grp Microondas & Radar E-28040 Madrid Spain USAF Res Lab Radar Signal Proc Branch Griffiss AFB NY 13441 USA

When trying to analyze a complex communication system, scientists often apply concepts from stochastic modeling and analysis to obtain a description of the system, frequently assuming that this will supplement our knowledge and improve our understanding. The philosophy is to obtain a result that would occur on the average, when this system is working under normal conditions. However, we must consider the fact that the introduction of probability in communication-system analysis often involves invoking certain assumptions and additional information about the system, which may not be valid. Hence, under these circumstances one may obtain a result that may not be commensurate with the conceived communication system. The objective of this paper is to highlight the basic assumptions that are invariably associated with the signal analysis in a system using stochastic analysis, and the introduction of probabilistic methods. Surprisingly, in many cases, analysis using stochastic methods may provide results equivalent to those obtained using deterministic methods. Examples are presented to illustrate our approach, and to explain the basic assumptions and formulate the mathematical framework associated with a stochastic analysis. We also demonstrate the equivalence between a random and a deterministic process, and under what conditions they approach the Cramer-Rao bound. Analysis using stochastic models to describe a system may be superior to a deterministic description. However, such a characterization comes with a large cost: namely, one must have more definitive knowledge about the system, knowledge that is often unavailable. For convenience, with the application of a random model, the concepts of stationarity and ergodicity are used to simplify the mathematical analysis of measured data. It is shown in this paper that the introduction of ergodicity in probability is similar to a deterministic analysis of a single waveform, and, in both cases, characterizes the entire unde

关键词： random process random variables deterministic analysis deterministic algorithms ergodic process communication systems adaptive systems probability stochastic process adaptive arrays adaptive signal processing

来源：评论

学校读者我要写书评

暂无评论

Coupling deterministic and Monte Carlo Transport Methods for the Simulation of Gamma-Ray Spectroscopy Scenarios

引用

IEEE TRANSACTIONS ON NUCLEAR SCIENCE 2008年第5期55卷 2598-2606页

作者： Smith, L. Eric Gesh, Christopher J. Pagh, Richard T. Miller, Erin A. Shaver, Mark W. Ashbaker, Eric D. Batdorf, Michael T. Ellis, J. Edward Kaye, William R. McConn, Ronald J. Meriwether, George H. Ressler, Jennifer J. Valsan, Andrei B. Wareing, Todd A. Pacific NW Natl Lab Richland WA 99352 USA Univ Michigan Nucl Engn & Radiol Sci Dept Ann Arbor MI 48105 USA Transpire Inc Gig Harbor WA 98335 USA

Simulation is often used to predict the response of gamma-ray spectrometers in technology viability and comparative studies for homeland and national security scenarios. Candidate radiation transport methods generally fall into one of two broad categories: stochastic (Monte Carlo) and deterministic. Monte Carlo methods are the most heavily used in the detection community and are particularly effective for calculating pulse-height spectra in instruments. However, computational times for scattering- and attenuation-dominated problems can be extremely long-many hours or more on a typical desktop computer. deterministic codes that discretize the transport in space, angle, and energy offer potential advantages in computational efficiency for these same kinds of problems, but pulse-height calculations are not readily accessible. This paper investigates a method for coupling angular flux data produced by a three-dimensional deterministic code to a Monte Carlo model of a gamma-ray spectrometer. Techniques used to mitigate ray effects, a potential source of inaccuracy in deterministic field calculations, are described. Strengths and limitations of the coupled methods, as compared to purely Monte Carlo simulations, are highlighted using example gamma-ray detection problems and two metrics: 1) accuracy when compared to empirical data and 2) computational time on a typical desktop computer.

关键词： deterministic algorithms gamma-ray spectroscopy modeling nuclear measurements radiation detectors radiation monitoring simulation

来源：评论

学校读者我要写书评

暂无评论

deterministic Massively Parallel Symmetry Breaking for Sparse Graphs 23

Deterministic Massively Parallel Symmetry Breaking for Spars...

引用

35th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Fischer, Manuela Giliberti, Jeff Grunau, Christoph Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450395458

We consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as measured by the standard notion of arboricity. For the problems of maximal independent set (MIS), maximal matching (MM), and vertex coloring, we improve the state of the art as follows. Let lambda denote the arboricity of the..-node input graph with maximum degree Delta. MIS andMM. We develop a low-space MPC algorithm that deterministically reduces the maximum degree to poly(lambda) in O(log log n) rounds, improving and simplifying the randomized O(log log n)-round poly(max(lambda, log n))-degree reduction of Ghaffari, Grunau, Jin [DISC'20]. Our approach when combined with the state-of-the-art O(log Delta + log log n)-round algorithm by Czumaj, Davies, Parter [SPAA'20, TALG'21] leads to an improved deterministic round complexity of O(log lambda + log log n). The above MIS and MM algorithm however works in the setting where the global memory allowed, i.e., the number of machines times the local memory per machine, is superlinear in the input size. We extend them to obtain the first low-space MIS and MM algorithms that work with linear global memory. Specifically, we show that both problems can be solved in deterministic time O(log lambda center dot log log(lambda) n), and even in O(log log n) time for graphs with arboricity at most log(O(1)) log n. In this setting, only a O(log(2) log n)-running time bound for trees was known due to Latypov and Uitto [ArXiv'21]. Vertex Coloring. We present a O(1)-round deterministic algorithm for the problem of O(lambda)-coloring in the linear-memory regime of MPC, with relaxed global memory of n center dot poly(lambda). This matches the round complexity of the state-of-the-art randomized algorithm by Ghaffari and Sayyadi [ICALP'19] and significantly improves upon the deterministic O(lambda(epsilon))-round algorithm by Barenboim and Khazanov [CSR'18]. Our algor

关键词： deterministic algorithms distributed computing massively parallel computation sparse graphs graph algorithms derandomization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：