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

6th International Conference on Intelligent Computing

作者： Formato, Richard A. POB 1714 Harwich MA 02645 USA

ISBN: (纸本)9783642149214

This note describes a simplified parameter free implementation of Central Force Optimization for use in deterministic multidimensional search and optimization The user supplies only the objective function to be maxi allied nothing mote The algorithm's performance is tested against a widely used suite of twenty three benchmark functions and compared to other state-of-the in algorithms CFO performs very well

关键词： Central Force Optimization CFO deterministic algorithm Multidimensional Search and Optimization Parameter-Free Optimization Gravitational Kinematics Metaphor Metaheuristic

来源：评论

学校读者我要写书评

暂无评论

Approximation Guarantees for deterministic Maximization of Submodular Function with a Matroid Constraint 1

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Sun, Xin Xu, Dachuan Guo, Longkun Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Qilu Univ Technol Shandong Acad Sci Sch Comp Sci & Technol Jinan 250353 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

ISBN: (数字)9783030592677

ISBN: (纸本)9783030592660;9783030592677

In the paper, we propose a deterministic approximation algorithm for maximizing a generalized monotone submodular function subject to a matroid constraint. The function is generalized through a curvature parameter c is an element of[0, 1], and essentially reduces to a submodular function when c = 1. Our algorithm employs the deterministic approximation devised by Buchbinder et al. [3] for the c = 1 case of the problem as a building block, and eventually attains an approximation ratio of 1+g(c)(x)+ Delta center dot [3+c-( 2+c)x-( 1+c)g(c)(x)] / 2+c+(1+c)(1-x) for the curvature parameter c is an element of[0, 1] and for a calibrating parameter that is any x is an element of[0, 1]. For c = 1, the ratio attains 0.5008 by setting x = 0.9, coinciding with the renowned performance guarantee of the problem. Moreover, when the submodular set function degenerates to a linear function, our generalized algorithm always produces optimum solutions and thus achieves an approximation ratio 1.

关键词： Submodular optimization Matroid constraint Curvature deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

deterministic Contention Resolution without Collision Detection: Throughput vs Energy 41

Deterministic Contention Resolution without Collision Detect...

引用

41st IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： De Marco, Gianluca Kowalski, Dariusz R. Stachowiak, Grzegorz Univ Salerno Dipartimento Informat Salerno Italy Augusta Univ Sch Comp & Cyber Sci Augusta GA USA SWPS Univ Sch Comp & Cyber Sci Warsaw Poland Univ Wroclaw Inst Comp Sci Wroclaw Poland

ISBN: (纸本)9781665445139

This paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of n stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel. We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations. We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption. While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption. Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating

关键词： Contention resolution deterministic algorithm Energy consumption Throughput

来源：评论

学校读者我要写书评

暂无评论

deterministic Network Exploration by Anonymous Silent Agents with Local Traffic Reports

Deterministic Network Exploration by Anonymous Silent Agents...

引用

39th International Colloquium on Automata, Languages, and Programming (ICALP)

作者： Dieudonne, Yoann Pelc, Andrzej Univ Picardie Jules Verne MIS Amiens France Univ Quebec Outaouais Dept Informat Quebec City PQ Canada

ISBN: (纸本)9783642315855

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to explore the network: every node must be visited by at least one agent and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. They are silent: they cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this weak model is impossible. Our aim is to solve the exploration problem giving to agents very restricted local traffic reports. Specifically, an agent that is at a node v in a given round, is provided with three bits of information, answering the following questions: Am I alone at v? Did any agent enter v in this round? Did any agent exit v in this round? We show that this small information permits to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric, i.e., in which there are agents with different views of the network. The algorithm works in time polynomial in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.

关键词： exploration deterministic algorithm anonymous mobile agent network graph

来源：评论

学校读者我要写书评

暂无评论

Superpixel-Based Two-View deterministic Fitting for Multiple-Structure Data 14th

Superpixel-Based Two-View Deterministic Fitting for Multiple...

引用

14th European Conference on Computer Vision (ECCV)

作者： Xiao, Guobao Wang, Hanzi Yan, Yan Suter, David Xiamen Univ Sch Informat Sci & Engn Fujian Key Lab Sensing & Comp Smart City Xiamen Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA Australia

ISBN: (纸本)9783319464664;9783319464657

This paper proposes a two-view deterministic geometric model fitting method, termed Superpixel-based deterministic Fitting (SDF), for multiple-structure data. SDF starts from superpixel segmentation, which effectively captures prior information of feature appearances. The feature appearances are beneficial to reduce the computational complexity for deterministic fitting methods. SDF also includes two original elements, i.e., a deterministic sampling algorithm and a novel model selection algorithm. The two algorithms are tightly coupled to boost the performance of SDF in both speed and accuracy. The key characteristic of SDF is that it can efficiently and deterministically estimate the parameters of model instances in multi-structure data. Experimental results demonstrate that the proposed SDF shows superiority over several state-of-the-art fitting methods for real images with single-structure and multiple-structure data.

关键词： deterministic algorithm Superpixel Model fitting Feature appearances

来源：评论

学校读者我要写书评

暂无评论

Random, deterministic, and Hybrid algorithms for Distributed Beamforming

Random, Deterministic, and Hybrid Algorithms for Distributed...

引用

5th Advanced Satellite Multimedia Systems Conference / 11th Signal Processing for Space Communications Workshop (ASMS/SPSC)

作者： Thibault, Ilaria Corazza, Giovanni E. Deambrogio, Lina Univ Bologna ARCES DEIS Viale Risorgimento 2 I-40136 Bologna Italy

ISBN: (纸本)9781424468331

Distributed beamforming is a form of cooperation among nodes in a wireless network to efficiently deliver a common message to a distant receiver. The critical requirement to achieve electromagnetic coherence is to synchronize the initial phases of all local oscillators, introducing minimal overhead and complexity. In the paper we introduce random, deterministic and hybrid algorithms, all based on feedback from the common receiver as the driving force, but with different phase update strategies. Our numerical results show that these algorithms achieve faster convergence time than previously proposed approaches.

关键词： array signal processing deterministic algorithm distant receiver distributed beamforming electromagnetic coherence feedback hybrid algorithm local oscillator message delivery radio networks radio receivers random algorithm wireless network

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Maximization of k-Submodular Function Under a Matroid Constraint

引用

Tsinghua Science and Technology 2024年第6期29卷 1633-1641页

作者： Yuezhu Liu Yunjing Sun Min Li School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm ***,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.

关键词： k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph

引用

algorithmICA 2006年第3期44卷 257-280页

作者： Ishii, T Nagamochi, H Ibaraki, T Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Kwansei Gakuin Univ Sch Sci & Technol Dept Informat Sanda 6691337 Japan

For two integers k, l > 0 and an undirected multigraph G = (V, E), we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected multigraph. In this paper we show that a (k - 1)-vertex-connected multigraph G can be made l-edge-connected and k-vertex-connected by adding at most max{l + 1, 2k - 4} surplus edges over the optimum in O( min{k,root n}kn(3) + n(4)) time, where n = vertical bar V vertical bar.

关键词： undirected multigraph edge-connectivity vertex-connectivity graph augmentation polynomial time approximation algorithm deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Adversarial Multiple Access Channels with Individual Injection Rates

引用

THEORY OF COMPUTING SYSTEMS 2017年第3期61卷 820-850页

作者： Anantharamu, Lakshmi Chlebus, Bogdan S. Rokicki, Mariusz A. Univ Colorado Denver Dept Comp Sci & Engn Denver CO 80217 USA Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

We study deterministic distributed broadcasting in synchronous multiple-access channels. Packets are injected into n nodes by a window-type adversary that is constrained by a window w and injection rates individually assigned to all nodes. We investigate what queue size and packet latency can be achieved with the maximum aggregate injection rate of one packet per round, depending on properties of channels and algorithms. We give a non-adaptive algorithm for channels with collision detection and an adaptive algorithm for channels without collision detection that achieve packet latency. We show that packet latency has to be either Omega(wmax(1,logw n)), when w n, or Omega(w + n), when w > n, as a matching lower bound to these algorithms. We develop a non-adaptive algorithm for channels without collision detection that achieves queue size and packet latency. This is in contrast with the adversarial model of global injection rates, in which non-adaptive algorithms with bounded packet latency do not exist (Chlebus et al. Distrib. Comput. 22(2), 93-116 2009). Our algorithm avoids collisions produced by simultaneous transmissions;we show that any algorithm with this property must have Omega(n w) packet latency.

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

来源：评论

学校读者我要写书评

暂无评论

On the Black-Box Complexity of Sperner's Lemma

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 629-646页

作者： Friedl, Katalin Ivanyos, Gabor Santha, Miklos Verhoeven, Yves F. Budapest Univ Technol & Econ H-1521 Budapest Hungary Hungarian Acad Sci Comp & Automat Res Inst H-1518 Budapest Hungary Univ Paris 11 CNRS LRI F-91405 Orsay France Natl Univ Singapore Ctr Quantum Technol Singapore 117543 Singapore Univ Paris 11 LRI F-91405 Orsay France ENST F-75013 Paris France

We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an O(root n) deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the Omega(root n) deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an Omega((4)root n) lower bound for its probabilistic, and an Omega((8)root n) lower bound for its quantum query complexity, showing that all these measures are polynomially related.

关键词： Query complexity Sperner's lemma deterministic algorithm Probabilistic and quantum lower bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：