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

An almost optimal algorithm for unbounded searching

Information Processing Letters 1976年第3期5卷 82-87页

作者： Bentley, Jon Louis Yao, Andrew Chi-Chih Department of Computer Science University of North Carolina Chapel Hill NC 27514 United States Department of Mathematics Massachussetts Institute of Technology Cambridge Massachussettes 02139 United States

来源：评论

学校读者我要写书评

暂无评论

PNOFA: Practical, Near-optimal Frame Aggregation for Modern 802.11 Networks 20

PNOFA: Practical, Near-Optimal Frame Aggregation for Modern ...

引用

23rd International Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems

作者： Abedi, Ali Brecht, Tim Abari, Omid Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada UCLA Comp Sci Dept Los Angeles CA USA

ISBN: (纸本)9781450381178

MAC-layer frame aggregation has significantly improved the efficiency of IEEE 802.11n/ac networks by placing multiple MAC-layer data units in a large PHY-layer frame. In this paper, we focus on finding the optimal length of an Aggregated MAC Protocol Data Unit (A-MPDU) in order to maximize throughput. This problem has proved to be extremely challenging because of the chain of dependencies between consecutive A-MPDUs due to software retransmissions and because error rates can be higher in the later part of the A-MPDU. In this paper we develop a model of A-MPDU frame aggregation and use it to design a statistically optimal algorithm. We then develop a standard compliant, Practical, Near-optimal Frame Aggregation algorithm (PNOFA). Our trace-based evaluation shows that across a variety of devices and scenarios PNOFA outperforms existing state-of-the-art algorithms and obtains throughputs that are within 97% of those obtained using the statistically optimal algorithm. Furthermore, we implement PNOFA on an 802.11ac Google Wifi access point. We find that when compared with the proprietary frame aggregation algorithm in the Qualcomm IPQ 4019 chipset's firmware, PNOFA increases average throughput by 17% in the scenarios tested.

关键词： WiFi 802.11 frame aggregation aggregated MAC protocol data unit A-MPDU length optimal algorithms performance evaluation

来源：评论

学校读者我要写书评

暂无评论

An optimal Algorithm for Finding the Kernel of a Polygon

引用

Journal of the ACM (JACM) 1979年第3期26卷 415-421页

作者： Lee, D.T. Preparata, F.P. University of Illinois Urbana-Champaign Urbana Illinois United States Coordinated Science Laboratory University of Illinois Urbana-Champaign Urbana IL 61801 United States

The kernel K(P) of a simple polygon P wah n verUces is the locus of the points internal to P from which all verUces of P are wslble Equwalently, K(P) is the mtersectmn of appropriate half-planes determined by the polygon's edges Although it is known that to find the intersection of n generic half-planes requires time O(n log n), we show that one can exploit the ordering of the half-planes corresponding to the sequence of the polygon's edges to obtain a kernel finding algorithm which runs m time O(n) and is therefore optimal. © 1979, ACM. All rights reserved.

关键词： computational complexity kernel of polygon optimal algorithms simple polygon

来源：评论

学校读者我要写书评

暂无评论

An optimal demand prepaging algorithm

引用

Information Processing Letters 1978年第3期7卷 132-136页

作者： Arora, Radha Krishan Subramanian, R.K. Computer Centre Indian Institute of Technology New Delhi 110 029 India

来源：评论

学校读者我要写书评

暂无评论

Update with out-of-sequence measurements in tracking: Exact solution

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2002年第3期38卷 769-778页

作者： Bar-Shalom, Y Univ Connecticut Dept Elect & Comp Engn Storrs CT 06269 USA

In target tracking systems measurements are typically collected in "scans" or "frames" and then they are transmitted to a processing center. In multisensor tracking systems that operate in a centralized manner, there are usually different time delays in transmitting the scans or frames from the various sensors to the center. This can lead to situations where measurements from the same target arrive out of sequence. Such "out-of-sequence" measurement (OOSM) arrivals can occur even in the absence of scan/frame communication time delays. The resulting "negative-time measurement update" problem, which is quite common in real multisensor systems, was solved previously only approximately in the literature. The exact state update equation, for such a problem is presented. The optimal and two suboptimal algorithms are compared on a number of realistic examples, including a GMTI (ground moving target indicator) radar case.

关键词： delays radar tracking sensor fusion target tracking GMTI radar ground moving target indicator multisensor tracking systems negative-time measurement update problem optimal algorithms out-of-sequence measurements suboptimal algorithms target tracking syst Multisensor systems Optimization algorithms Sensor fusion Moving target detector radar target tracking Target tracking delay

来源：评论

学校读者我要写书评

暂无评论

Scheduling for electricity cost in a smart grid

引用

JOURNAL OF SCHEDULING 2016年第6期19卷 687-699页

作者： Burcea, Mihai Hon, Wing-Kai Liu, Hsiang-Hsuan Wong, Prudence W. H. Yau, David K. Y. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Singapore Univ Technol & Design Informat Syst Technol & Design Singapore Singapore

We study an offline scheduling problem arising in demand response management in a smart grid. Consumers send in power requests with a flexible set of timeslots during which their requests can be served. For example, a consumer may request the dishwasher to operate for 1 h during the periods 8am to 11am or 2pm to 4pm. The grid controller, upon receiving power requests, schedules each request within the specified duration. The electricity cost is measured by a convex function of the load in each timeslot. The objective of the problem is to schedule all requests with the minimum total electricity cost. As a first attempt, we consider a special case in which the power requirement and the duration a for which a request needs service are both unit-size. For this problem, we present a polynomial time offline algorithm that gives an optimal solution and shows that the time complexity can be further improved if the given set of timeslots forms a contiguous interval.

关键词： Optimization Convex power cost optimal algorithms Time complexity Feasible graph

来源：评论

学校读者我要写书评

暂无评论

Energy consumption balancing in multi-interface networks

引用

JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING 2020年第8期11卷 3209-3219页

作者： Aloisio, Alessandro Navarra, Alfredo Mostarda, Leonardo Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat Laquila Italy Gran Sasso Sci Inst Laquila Italy Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 Perugia Italy Univ Camerino Scuola Sci & Tecnol Macerata Italy

In heterogeneous networks, devices can communicate by means of multiple interfaces. By choosing which interfaces to activate (switch-on) at each device, several connections might be established. A connection is established when the devices at its endpoints share at least one active interface. Interfaces are associated with a cost defining the percentage of energy consumed to switch-on the corresponding interface. In this paper, we consider the case where each device is limited to activate at most a fixed numberpof its available interfaces in order to accomplish the required task. In particular, we consider the so-called Coverage problem. Given a networkG=(V,E) nodesVrepresent devices, edgesErepresent connections that can be established. The aim is to activate at mostpinterfaces at each node in order to establish all the connections defined byE. Parameterpimplies a sort of balanced consumption among devices so that none of them suffers-in terms of consumed energy-for being exploited in the network more than others. We provide aNP-completeness proof for the feasibility of the problem even considering the basic case ofp=2and unitary costs for all the interfaces. That is, each interface costs the same as all the others. Then we provide optimal algorithms that solve the problem in polynomial time for different graph topologies and general costs associated to the interfaces.

关键词： Multi-interface networks Energy optimization NP-completeness optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Liberating the dimension for function approximation

引用

JOURNAL OF COMPLEXITY 2011年第1期27卷 86-110页

作者： Wasilkowski, G. W. Wozniakowski, H. Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math Warsaw Poland

We study approximation of functions that may depend on infinitely many variables. We assume that such functions belong to a separable weighted Hilbert space that is the direct sum of tensor product Hilbert spaces of functions with finitely many variables. The weight sequence gamma = {gamma(u)} is used to moderate the influence of terms depending on finitely many variables from u. We consider algorithms that use finitely many arbitrary linear functionals. Each linear functional is an inner product whose cost depends on the number of active variables of the inner product generator. That is, if the generator has d active variables then the cost is $(d) for a given non-decreasing function $. The error of an algorithm is defined in the worst case setting in a norm given by weighted L-2 norms for terms depending on finitely many variables. The epsilon-complexity is understood as the minimal cost among all algorithms with errors at most epsilon. We are especially interested in polynomial tractability, where the epsilon-complexity is bounded by a polynomial in epsilon(-1), and weak tractability, where the epsilon-complexity is sub-exponential in epsilon(-1). The results are as follows. An algorithm whose cost is equal to the epsilon-complexity. It turns out the algorithm does not depend on the cost function $. Necessary and sufficient conditions on polynomial tractability. It turns out that we may have polynomial tractability even when $(d) is exponential in d. This holds since the minimal number of active variables that must be used to compute an epsilon-approximation may be surprisingly small, e.g., o(In(epsilon(-1))) or even smaller. Necessary and sufficient conditions on weak tractability. It turns out that we have two quite different cases depending on whether the largest eigenvalue for the univariate case is simple or not. We may have weak tractability even when $(d) is doubly exponential in d. Specializing tractability conditions for product and finite-order weights.

关键词： Multivariate function approximation Path integration optimal algorithms Complexity Tractability

来源：评论

学校读者我要写书评

暂无评论

Simple Monte Carlo and the metropolis algorithm

引用

JOURNAL OF COMPLEXITY 2007年第4-6期23卷 673-696页

作者： Mathe, Peter Novak, Erich Univ Jena Math Inst D-07743 Jena Germany Weierstrass Inst Appl Anal & Stochast D-10117 Berlin Germany

We study the integration of functions with respect to an unknown density. Information is available as oracle calls to the integrand and to the non-normalized density function. We are interested in analyzing the integration error of optimal algorithms (or the complexity of the problem) with emphasis on the variability of the weight function. For a corresponding large class of problem instances we show that the complexity grows linearly in the variability, and the simple Monte Carlo method provides an almost optimal algorithm. Under additional geometric restrictions (mainly log-concavity) for the density functions, we establish that a suitable adaptive local Metropolis algorithm is almost optimal and outperforms any non-adaptive algorithm. (c) 2007 Elsevier Inc. All rights reserved.

关键词： Monte Carlo methods metropolis algorithm log-concave density rapidly mixing Markov chains optimal algorithms adaptivity complexity

来源：评论

学校读者我要写书评

暂无评论

A FAST SELECTION ALGORITHM FOR MESHES WITH MULTIPLE BROADCASTING

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第7期5卷 772-778页

作者： BHAGAVATHI, D LOOGES, PJ OLARIU, S SCHWING, JL ZHANG, J OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 ELIZABETH CITY STATE UNIV DEPT MATH & COMP SCIELIZABETH CITYNC 27909

One of the fundamental algorithmic problems in computer science involves selecting the kth smallest element in a collection A of n elements. We propose an algorithm design methodology to solve the selection problem on meshes with multiple broadcasting. Our methodology leads to a selection algorithm that runs in O(n1/8(log n)3/4) time on a mesh with multiple broadcasting of size n3/8(log n)1/4 X n5/8/(log n)1/4 . This result is optimal over a large class of selection algorithms. Our result shows that just as for semigroup computations, selection can be done faster on suitably chosen rectangular meshes than on square meshes.

关键词： MESH WITH MULTIPLE BROADCASTING SELECTION QUERY PROCESSING DATABASES ALGORITHM DESIGN METHODOLOGIES PARALLEL algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：