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

Advice complexity of adaptive priority algorithms

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Boyar, Joan Larsen, Kim S. Pankratov, Denis Department of Mathematics and Computer Science University of Southern Denmark Denmark Department of Computer Science and Software Engineering Concordia University QC Canada

The priority model was introduced to capture \greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. We also present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way. Copyright © 2019, The Authors. All rights reserved.

关键词： adaptive algorithms

A DETERMINISTIC ANALYSIS OF LINEARLY CONSTRAINED adaptive FILTERING algorithms

学校读者我要写书评

暂无评论

A DETERMINISTIC ANALYSIS OF LINEARLY CONSTRAINED ADAPTIVE FI...

European Signal Processing Conference

作者： Masahiro Yukawa Isao Yamada Department of Electrical and Electronic Engineering Niigata University Department of Communications and Integrated Systems Tokyo Institute of Technology

This paper presents a mathematically rigorous analysis of linearly constrained adaptive filtering algorithms based on the adaptive projected subgradient method. We provide the novel concept of constraint-embedding functions that enables to analyze certain classes of linearly constrained adaptive algorithms in a unified manner. Trajectories of the linearly constrained adaptive filters always lie in the affine constraint set, a translation of a closed subspace. Based on this fact, we translate all the points on the constraint set to its underlying subspace - which we regard as a Hilbert space - thereby making the analysis feasible. Derivations of the linearly constrained adaptive filtering algorithms are finally presented in connection with the analysis.

关键词： Signal processing algorithms Algorithm design and analysis Convex functions adaptive algorithms Hilbert space Signal processing Vectors

Efficient and adaptive parameterized algorithms on modular decompositions

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Kratsch, Stefan Nelles, Florian Department of Computer Science Humboldt-Universität zu Berlin Germany

We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as maximum matching, triangle counting, and maximum s-t vertex-capacitated flow. The modular-width of a graph depends on its (unique) modular decomposition tree, and can be computed in linear time O(n+ m) for graphs with n vertices and m edges. Modular decompositions are an important tool for graph algorithms, e.g., for linear-time recognition of certain graph classes. Throughout, we obtain efficient parameterized algorithms of running times O(f(mw)n+m), O(n + f(mw)m) , or O(f(mw) + n + m) for graphs of modular-width mw. Our algorithm for maximum matching, running in time O(mw2 logmw n + m), is both faster and simpler than the recent O(mw4 n + m) time algorithm of Coudert et al. (SODA 2018). For several other problems, e.g., triangle counting and maximum b-matching, we give adaptive algorithms, meaning that their running times match the best unparameterized algorithms for worst-case modular-width of mw = Θ(n) and they outperform them already for mw = o(n), until reaching linear time for mw = O(1). Copyright © 2018, The Authors. All rights reserved.

关键词： adaptive algorithms

Finite form realizations of adaptive control algorithms

学校读者我要写书评

暂无评论

Finite form realizations of adaptive control algorithms

European Control Conference (ECC)

作者： Ivan Tyukin Danil Prokhorov Cees van Leeuwen RIKEN Brain Science Institute Wako-shi Saitama Japan Ford Research Laboratory Dearborn MI U.S.A.

We suggest a new method to design adaptation algorithms that guarantee improved performance and are applicable for a class of plants with nonconvex parameterization. The main idea of the method is, first, to augment the tuning error (possibly using uncertainty-dependent signals) of the known adaptive schemes in such a way that the desired characteristics of the adaptive system are guaranteed. Then we search for realization of the proposed schemes in an integral-differential form similar to the PI (proportional-integral) rules. Such adaptation schemes in the paper are called adaptive algorithms in finite forms. For this new description, neither dependence on state derivatives, nor unknown parameters is required. Sufficient conditions for existence of new finite form realizations of adaptive algorithms are proposed.

关键词： Mathematical model adaptive control Algorithm design and analysis Heuristic algorithms adaptive algorithms Differential equations Tuning

adaptive suppression algorithms in asynchronous cdma for cellular and indoor wireless channels

学校读者我要写书评

暂无评论

Adaptive suppression algorithms in asynchronous cdma for cel...

IEEE International Conference on Consumer Electronics (ICCE)

作者： M. Tahemezhadi A. Thomas M. Vora Department of Electrical Engineering Northern Illinois University DeKalb IL USA U.S. Robotics Inc. Skokie IL USA

On the SDEs and Scaling Rules for adaptive Gradient algorithms

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Malladi, Sadhika Lyu, Kaifeng Panigrahi, Abhishek Arora, Sanjeev Department of Computer Science Princeton University United States

Approximating Stochastic Gradient Descent (SGD) as a Stochastic Differential Equation (SDE) has allowed researchers to enjoy the benefits of studying a continuous optimization trajectory while carefully preserving the stochasticity of SGD. Analogous study of adaptive gradient methods, such as RMSprop and Adam, has been challenging because there were no rigorously proven SDE approximations for these methods. This paper derives the SDE approximations for RMSprop and Adam, giving theoretical guarantees of their correctness as well as experimental validation of their applicability to common large-scaling vision and language settings. A key practical result is the derivation of a square root scaling rule to adjust the optimization hyperparameters of RMSprop and Adam when changing batch size, and its empirical validation in deep learning settings. © 2022, CC BY.

关键词： adaptive algorithms

Bounds for the number of tests in non-adaptive randomized algorithms for group testing

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bshouty, Nader H. Haddad, George Haddad-Zaknoon, Catherine A. Technion Haifa Israel Orthodox Arab College Grade 11 Haifa Israel

We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a modelM, let mM(n, d) be the minimum number of tests required to detect at most d defectives within n items, with success probability at least 1 - δ, for some constant δ. In this paper, we study the measures (equation presented) In the literature, the analyses of such models only give upper bounds for cM(d) and cM, and for some of them, the bounds are not tight. We give new analyses that yield tight bounds for cM(d) and cM for all the known models M. Copyright © 2019, The Authors. All rights reserved.

关键词： adaptive algorithms

adaptive Asynchronous Gossip algorithms for Consensus in Heterogeneous Sensor Networks

学校读者我要写书评

暂无评论

IEEE Internet of Things Journal 2025年

作者： Ilic, Nemanja Vucetic, Miljan Makarov, Aleksej Petrovic, Ranko Punt, Marija College of Applied Technical Sciences School of Computing Union University Kruševac Belgrade Serbia Vlatacom Institute Belgrade Serbia VŠB - Technical University of Ostrava Ostrava Czech Republic University Singidunum Belgrade Serbia University of Belgrade School of Electrical Engineering Belgrade Serbia

The Internet of Things (IoT) connects a wide range of sensors and devices in environments that are often dynamic and resource-constrained, where efficient distributed solutions are essential for ensuring robust and scalable operation. This paper presents a novel adaptive consensus algorithm, tailored for distributed signal processing in heterogeneous sensor networks, with a focus on distributed estimation and target tracking. The algorithm addresses the challenge posed by networks where intelligent sensors have limited sensing, computation and communication capabilities, resulting in diverse quality of locally available information, and leading to neighbor-based information exchanges. It employs asynchronous gossip protocols to randomly exchange information between nodes, ensuring robustness to time synchronization and network topology uncertainties, while limiting computational and communication costs. The adaptation mechanism operates in two complementary ways. Firstly, we account for variations in the quality of local processing results, ensuring that asymptotic behavior of the consensus scheme accurately reflects this diversity. Secondly, we introduce a novel adaptation of the rates at which nodes initiate communication, using the available local information. This enables fast information dissemination, and provides a solution that is both effective and efficient. We show that, under appropriate network connectivity assumptions, the results obtained by the algorithm converge to the desired asymptotic values in the mean square sense. Numerical simulations demonstrate the algorithm's properties and effectiveness, particularly in modeling visual surveillance networks where fixed cameras are augmented by moving drones to extend the coverage area. © 2025 IEEE.

关键词： adaptive algorithms

adaptive Object Detection for Indoor Navigation Assistance: A Performance Evaluation of Real-Time algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pratap, Abhinav Kumar, Sushant Chakravarty, Suchinton Department of Computer Science and Engineering ASET Amity University Noida India

This study addresses the critical need for accurate and efficient object detection in assistive technologies for visually impaired individuals. We systematically evaluate the performance of four prominent real-time object detection algorithms—YOLO, SSD, Faster R-CNN, and Mask R-CNN—within the context of indoor navigation assistance. Our analysis, conducted on the Indoor Objects Detection dataset, focuses on key parameters including detection accuracy, processing speed, and adaptability to the unique challenges of indoor environments. The findings highlight the crucial trade-off between precision and processing efficiency, providing valuable insights for selecting optimal algorithms for real-time assistive navigation systems. This research contributes to a deeper understanding of adaptive machine learning applications that can significantly improve indoor navigation solutions for the visually impaired, promoting inclusivity and accessibility. © 2025, CC BY.

关键词： adaptive algorithms