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

Drone-Based Bug Detection in Orchards with Nets: A Novel Orienteering Approach

ACM TRANSACTIONS ON SENSOR NETWORKS 2024年第3期20卷 1-28页

作者： Sorbelli, Francesco Betti Coro, Federico Das, Sajal K. Palazzetti, Lorenzo Pinotti, Cristina M. Univ Perugia Comp Sci & Math I-06123 Perugia Italy Univ Padua Math Via VIII Febbraio 2 I-35122 Padua Italy Missouri Univ Sci & Technol Dept Comp Sci 106300 W 13th St Rolla MO 65401 USA Univ Florence Comp Sci Piazza San Marco 4 I-50121 Florence Italy

The use of drones for collecting information and detecting bugs in orchards covered by nets is a challenging problem. The nets help in reducing pest damage, but they also constrain the drone's flight path, making it longer and more complex. To address this issue, we model the orchard as an aisle-graph, a regular data structure that represents consecutive aisles where trees are arranged in straight lines. The drone flies close to the trees and takes pictures at specific positions for monitoring the presence of bugs, but its energy is limited, so it can only visit a subset of positions. To tackle this challenge, we introduce the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the orienteering problem, where likely infested locations are prioritized by assigning them a larger profit. Additionally, the drone's movements have a cost in terms of energy, and the objective is to plan a drone's route in the most profitable locations under a given drone's battery. We show that SOAP can be optimally solved in polynomial time, but for larger orchards/instances, we propose faster approximation and heuristic algorithms. Finally, we evaluate the algorithms on synthetic and real datasets to demonstrate their effectiveness and efficiency.

关键词： Aisle-graph drones orchard bug detection approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Better approximation algorithms for the graph diameter

Better approximation algorithms for the graph diameter

引用

25th Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2014

作者： Chechik, Shiri Larkin, Daniel H. Roditty, Liam Schoenebeck, Grant Tarjan, Robert E. Williams, Virginia Vassilevska Microsoft Research SVC United States Princeton University United States Bar Ilan University Israel University of Michigan United States Microsoft Research SVC Princeton University United States Stanford University United States

ISBN: (纸本)9781611973389

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in Õ (n2 + m√n) time an estimate D˜ for the diameter D in directed graphs with nonnega- Tive edge weights, such that [2/3 · D]-(M - I) ≤ D˜ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to Õ (m√;n). Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no O(n2-Ε) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than 3/2. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine 3/2-approximation for the diameter, one running in Õ (m3/2)time, and one running in Õ (mn 2/3 ) time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 - Ε)-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c-approximation for the diameter, i.e. an estimate D˜ such that D - c ≤ D˜ ≤ D˜. An extremely simple Õ (mn1-Ε) time algorithm achieves an additive n Ε- approximation;no better results are known. We show that for any Ε > 0, getting an additive nΕ-approximation algorithm for the diameter running in O (n2-δ) time for any δ > 2Ε would falsify the Strong Exponential Time Hypothesis. Thus t

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Near linear time 5/3-approximation algorithms for two-level power assignment problems 10

Near linear time 5/3-approximation algorithms for two-level ...

引用

2014 10th ACM International Workshop on Foundations of Mobile Computing, FOMC 2014

作者： Grimmer, Benjamin Qiao, Kan Department of Computer Science Illinois Institute of Technology ChicagoIL United States

ISBN: (纸本)9781450329866

We investigate the problem of assigning power levels to nodes of an ad hoc network to minimize total power while preserving connectivity. We consider a simplified version of this problem by requiring bidirected input graphs (ie if an arc uv exists, then the arc vu exists and has the same cost) and that all arcs have cost 0 or 1. This corresponds to a network where each transmitter can operate at high and low power. There are two versions of this problem, a symmetric variant which seeks a connected spanning subgraph and includes an edge in the subgraph if both endpoints have power at least the edge cost, and an asymmetric variant which seeks a strongly connected spanning subgraph and includes an arc in the subgraph if the source endpoint has power at least the arc cost. Both of these have been shown to be NP-Complete. We present 5/3-approximation algorithms for each of these that run in 0(mα(n)) where α(n) is the inverse Ackermann function.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On Minimizing Total Discounted Cost in MDPs Subject to Reachability Constraints

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第9期69卷 6466-6473页

作者： Savas, Yagiz Verginis, Christos K. Hibbard, Michael Topcu, Ufuk Univ Texas Austin Austin TX 78712 USA

In this article, we study the synthesisof a policy in a Markov decision process (MDP) following which an agent reaches a target state in the MDP while minimizing its total discounted cost. The problem combines a reachability criterion with a discounted cost criterion and naturally expresses the completion of a task with probabilistic guarantees and optimal transient performance. We first establish that an optimal policy for the considered formulation may not exist but that there always exists a near-optimal stationary policy. We additionally provide a necessary and sufficient condition for the existence of an optimal policy. We then restrict our attention to stationary deterministic policies and show that the decision problem associated with the synthesis of an optimal stationary deterministic policy is NP-complete. Finally, we provide an exact algorithm based on mixed-integer linear programming and propose an efficient approximation algorithm based on linear programming for the synthesis of an optimal stationary deterministic policy.

关键词： Costs Probabilistic logic Task analysis Planning approximation algorithms Trajectory Markov decision processes Discounting Markov decision processes (MDPs) optimization reachability

来源：评论

学校读者我要写书评

暂无评论

Non-Iterative Solution for Coordinated Optimal Dispatch via Equivalent Projection-Part II: Method and Applications

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2024年第1期39卷 899-908页

作者： Tan, Zhenfei Yan, Zheng Zhong, Haiwang Xia, Qing Shanghai Jiao Tong Univ Minist Educ Key Lab Control Power Transmiss & Convers Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Shanghai Noncarbon Energy Convers & Utilizat Inst Shanghai 200240 Peoples R China Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China Tsinghua Univ Sichuan Energy Internet Res Inst Beijing 100084 Peoples R China

This two-part paper develops a non-iterative coordinated optimal dispatch framework, i.e., free of iterative information exchange, via the innovation of the equivalent projection (EP) theory. The EP eliminates internal variables from technical and economic operation constraints of the subsystem and obtains an equivalent model with reduced scale, which is the key to the non-iterative coordinated optimization. In Part II of this paper, a novel projection algorithm with the explicit error guarantee measured by the Hausdorff distance is proposed, which characterizes the EP model by the convex hull of its vertices. This algorithm is proven to yield a conservative approximation within the prespecified error tolerance and can obtain the exact EP model if the error tolerance is set to zero, which provides flexibility to balance the computation accuracy and effort. Applications of the EP-based coordinated dispatch are demonstrated based on the multi-area coordination and transmission-distribution coordination. Case studies with a wide range of system scales verify the superiority of the proposed projection algorithm in terms of computational efficiency and scalability, and validate the effectiveness of the EP-based coordinated dispatch in comparison with the joint optimization.

关键词： Measurement approximation algorithms Power systems Computational modeling Computational efficiency Solid modeling Measurement uncertainty Coordinated optimization non-iterative multi-area dispatch distribution network projection

来源：评论

学校读者我要写书评

暂无评论

Differentially Private Bipartite Consensus Over Signed Networks With Time-Varying Noises

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第9期69卷 5788-5803页

作者： Wang, Jimin Ke, Jieming Zhang, Ji-Feng Univ Sci & Technol Beijing Sch Automat & Elect Engn Beijing 100083 Peoples R China Minist Educ Key Lab Knowledge Automat Ind Proc Beijing 100083 Peoples R China Chinese Acad Sci Inst Syst Sci Acad Math & Syst Sci Key Lab Syst & Control Beijing 100190 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China

This article investigates the differentially private bipartite consensus problem over signed networks. To solve this problem, a new algorithm is proposed by adding noises with time-varying variances to the cooperative-competitive interactive information. In order to achieve the privacy protection, the variances of the added noises are allowed to increase, which are substantially different from the existing works. In addition, the variances of the added noises can be either decaying or constant. By using a time-varying step-size based on the stochastic approximation method, we show that the algorithm converges in mean-square and almost-surely even with increasing privacy noises. We further develop a method to design the step-size and the noise parameter, affording the algorithm to achieve the average bipartite consensus with the desired accuracy and the predefined differential privacy level. Moreover, we give the mean-square and almost-sure convergence rates of the algorithm, and the privacy level with different forms of the privacy noises. We also reveal the tradeoff between the accuracy and the privacy, and extend the results to local differential privacy. Finally, a numerical example verifies the theoretical results and demonstrates the algorithm's superiority against existing methods.

关键词： Privacy Convergence Differential privacy Consensus algorithm approximation algorithms Social networking (online) Consensus control Convergence rate differential privacy multiagent system signed network stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

ROBUST FACTORIZATIONS AND COLORINGS OF TENSOR GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第1期38卷 883-916页

作者： Brakensiek, Joshua Davies, Sami Stanford Univ Stanford CA 94305 USA Univ Calif Berkeley Berkeley CA 94720 USA

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3 -coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the no(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3 -coloring of random graphs, and Arora and Ge studied the 3 -coloring of graphs with low threshold -rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3 -coloring problem. We consider graphs of the form H = (V,E) with V = V(K3 \times G) and E = E(K3 \times G) \setminus E', where E' \subseteq E(K3 \times G) is any edge set such that no vertex has more than an \epsilon -fraction of its edges in E'. We show that one can construct H widetilde \= K3 \times Gwidetilde \ with V(Hwidetilde \) = V(H) that is close to H. For arbitrary G, Hwidetilde \ satisfies lE(H)\DeltaE(Hwidetilde\)l \leqO(\epsilonlE(H)l). Additionally, when G is a mild expander, we provide a 3 -coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP -hard to 3 -color H.

关键词： graph reconstruction tensor factorization 3-coloring approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint Detection and Channel Estimation for MIMO-OTFS Systems

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2024年第8期73卷 11568-11579页

作者： Shi, Ce Zhao, Lei Cui, Yanpeng Chu, Yueyan Guo, Wenbin Wang, Wenbo Beijing Univ Posts & Telecommun Sch Informat & Commun Engn Beijing 100876 Peoples R China Minist Educ Key Lab Universal Wireless Commun Beijing 100816 Peoples R China

MIMO orthogonal time frequency space (OTFS) modulation is considered a promising communication technology for future ultra-high-speed vehicular scenarios. However, the high complexity channel estimator and low accuracy symbol detection algorithm hinder the development of OTFS modulation. Unlike the conventional receiver, channel estimation and symbol detection are relatively isolated, we design a novel joint receiver combining channel estimation and symbol detection exploiting a partial iterative feedback mechanism. Firstly, we take into account the effect of fractional Doppler and make it approximate gridding. Therefore, the channel estimation problem is transformed into a block sparse signal recovery problem, and an efficient sparse adaptive block orthogonal matching pursuit (ABOMP) algorithm is proposed. Secondly, we propose a low-complexity approximate message passing (AMP) algorithm, which provides a reference for selecting high-confidence data symbols and reduces the redundant calculation of multiple detections. Finally, a partial iteration feedback joint detection and channel estimation (JDCE) algorithm is proposed to further reduce the system bit error ratio (BER) and computational complexity. Comprehensive simulation experiments are conducted and demonstrate the effectiveness and superiority of the proposed algorithm.

关键词： Channel estimation Symbols Iterative methods OFDM Complexity theory Sparse matrices approximation algorithms MIMO-OTFS sparse recovery approximate message passing channel estimation symbol detection

来源：评论

学校读者我要写书评

暂无评论

High Efficiency Multiply-Accumulator Using Ternary Logic and Ternary Approximate Algorithm

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2024年

作者： Wen, Wanting Zhao, Guangchao Hu, Wanbo Li, Ziye Wang, Xingli Friedman, Eby G. Tay, Beng Kang Ke, Shaolin Huang, Mingqiang Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Wuhan Inst Technol Hubei Key Lab Opt Informat & Pattern Recognit Wuhan 430205 Peoples R China Nanyang Technol Univ Ctr Micro & Nanoelect CMNE Sch Elect & Elect Engn Singapore 639798 Singapore Univ Rochester Dept Elect & Comp Engn Rochester NY 14627 USA

A multiply-accumulator, often abbreviated as a MAC unit, is central to a multitude of computational tasks, particularly those tasks (such as neural networks) involving array-based mathematical computations. The quest for novel methods to efficiently store and process data in a MAC has become imperative. Recently, ternary logic has attracted significant attention due to its higher information density than conventional binary systems. However, though numerous studies have showcased ternary arithmetic circuits, advancements in ternary-based vector processing have been notably scarce. To bridge this gap, this work undertakes comprehensive study into the optimization of ternary MAC units. Firstly, we propose various ternary approximate algorithms which shows 30%-less power consumption and only 2% computation error when compared with the accurate design. Secondly, we design sophisticated ternary circuits and obtain 74% similar to 80% lower power-delay-product (PDP) than previous works. Finally, we evaluate the proposed ternary MAC unit using both carbon-nanotube field-effect transistor (CNTFET) and silicon-based 180 nm CMOS processes. The simulation results show the ternary circuit is better than binary circuit in terms of both area (similar to 45% less) and power ( similar to 30% less), highlighting its strong potential for practical applications.

关键词： Circuits Multivalued logic Adders CNTFETs Accuracy Transistors Encoding approximation algorithms Threshold voltage Performance evaluation Ternary logic circuit multiplying-accumulator approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Consensus Iterated Posterior Linearization Filter for Distributed State Estimation

引用

IEEE SIGNAL PROCESSING LETTERS 2025年 32卷 561-565页

作者： Garcia-Fernandez, Angel F. Battistelli, Giorgio Univ Liverpool Dept Elect Engn & Elect Liverpool L69 3GJ England Univ Firenze Dipartimento Ingn Informaz DINFO I-50139 Florence Italy

This paper presents the consensus iterated posterior linearisation filter (IPLF) for distributed state estimation. The consensus IPLF algorithm is based on a measurement model described by its conditional mean and covariance given the state, and performs iterated statistical linear regressions of the measurements with respect to the current approximation of the posterior to improve estimation performance. Three variants of the algorithm are presented based on the type of consensus that is used: consensus on information, consensus on measurements, and hybrid consensus on measurements and information. Simulation results show the benefits of the proposed algorithm in distributed state estimation.

关键词： Covariance matrices approximation algorithms Vectors Kalman filters Signal processing algorithms Sensors Consensus algorithm State estimation Current measurement Noise measurement Consensus distributed state estimation iterated posterior linearisation nonlinear filtering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：