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

Gradient-Based Discrete-Time Concurrent Learning for Standalone Function approximation

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2020年第2期65卷 749-756页

作者： Djaneye-Boundjou, Ouboti Ordonez, Raul Univ Dayton Dept Elect & Comp Engn Dayton OH 45469 USA

When using standard learning techniques for uncertainty approximation, persistently exciting inputs are necessary in order to achieve good parameter estimation. It has been shown in recent years that, through concurrent learning (CL), it is possible to achieve better learning without requiring persistency of excitation. We define good learning here by how well an uncertainty can be reconstructed given the estimated parameters. Most studies concerning CL have however been done in the continuous-time (CT) framework. While working with discrete-time (DT) structured uncertainties, we have shown in an earlier study that the concept of CL could be used to solve the parameter identification problem granted, much like in the CT domain, a less restrictive condition compared to that of persistency of excitation is verified. This paper furthers our fundamental study of CL in the DT framework while drawing comparisons with the traditional but fundamental gradient descent technique. As a main contribution, via formal derivations, we present a generalized gradient-based CL motivated DT algorithm for online approximation of both DT structured and unstructured uncertainties. Numerical simulations are provided to show how well the designed algorithm leverages memory usage to achieve better learning.

关键词： Uncertainty Function approximation approximation algorithms Convergence Computational modeling Symmetric matrices Linear algebra Function approximation learning system identification

来源：评论

学校读者我要写书评

暂无评论

Pseudorandom Generators, Resolution and Heavy Width 22

Pseudorandom Generators, Resolution and Heavy Width

引用

37th Computational Complexity Conference, CCC 2022

作者： Sokolov, Dmitry St. Petersburg State University Russia St. Petersburg Department of Steklov Mathematical Institute Russian Academy of Sciences Russia

ISBN: (纸本)9783959772419

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson [2] we call a pseudorandom generator F : {0, 1}n → {0, 1}m hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement b ∈/ Im(F) for any string b ∈ {0, 1}m. In [2] the authors suggested the "functional encoding" of the considered statement for Nisan–Wigderson generator that allows the introduction of "local" extension variables. These extension variables may potentially significantly increase the power of the proof system. In [2] authors gave a lower bound of exp [Ω (n2/m·22∆)] on the length of Resolution proofs where ∆ is the degree of the dependency graph of the generator. This lower bound meets the barrier for the restriction technique. In this paper, we introduce a "heavy width" measure for Resolution that allows us to show a lower bound of exp [n2/m2O(Ε∆)] on the length of Resolution proofs of the considered statement for the Nisan–Wigderson generator. This gives an exponential lower bound up to ∆:= log2−δ n (the bigger degree the more extension variables we can use). In [2] authors left an open problem to get rid of scaling factor 22∆ , it is a solution to this open problem. © Dmitry Sokolov

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Bandwidth resource allocation in integrated access and backhaul networks

Bandwidth resource allocation in integrated access and backh...

引用

2022 ACM SIGCOMM Workshop on 5G and Beyond Network Measurements, Modeling, and Use Cases, 5G-MeMU 2022, co-located with ACM SIGCOMM 2022

作者： Harris, Dor Raz, Danny Sagiv, Peer Techion Haifa Israel

ISBN: (纸本)9781450393935

One of the promising technologies that allows currently deployed 5G and the anticipated 6G networks to cope with the ever increasing demand for high throughput low latency data services is Integrated Access and Backhaul. Self driving cars, augmented reality games and large scale data streaming are simple examples of new applications that require a large amount of low latency traffic. Integrated Access and Backhaul can provide better service to such applications by extending the traditional cellular access and combining access and backhaul resources. However, the actual performance gain depends on the specific allocation of the radio resources. In this paper we address this challenge and study new ways to allocate bandwidth across such networks. We formulate the IAB Resource Allocation Problem (IABrap) and provide a novel approximation algorithm with guaranteed performance to solve it. We also study a new, ML method, that is based on applying GNN (Graph Neural Network) to this problem. We evaluate the expected performance of both methods in realistic scenarios using a self-developed network simulator. Our results indicate that combining traditional algorithmic techniques with state of art ML can provide better practical algorithms. © 2022 ACM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

RSS-Based Byzantine Fault-Tolerant Localization Algorithm Under NLOS Environment

引用

IEEE COMMUNICATIONS LETTERS 2021年第2期25卷 474-478页

作者： Mei, Xiaojun Wu, Huafeng Xian, Jiangfeng Chen, Bowen Shanghai Maritime Univ Merchant Marine Coll Shanghai 201306 Peoples R China Univ Lisbon Inst Syst & Robot Inst Super Tecn P-1049001 Lisbon Portugal Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy Linnaeus Univ Dept Informat S-35106 Vaxjo Sweden

Localization is one of the most critical tasks in wireless sensor networks, but achieving a relatively accurate location estimation is challenging when there have Byzantine fault and non-line-of-sight (NLOS) bias simultaneously. In this context, a localization method, based on received signal strength (RSS), is proposed in this letter to mitigate the impact of Byzantine fault and NLOS bias on the localization accuracy of wireless sensor networks. The proposed method relies on a Byzantine fault-tolerant localization algorithm (BFLA), which converts the localization problem into a generalized trust-region subproblem (GTRS) by applying certain approximations. In order to obtain a feasible solution to the GTRS, a block-coordinate update (BCU) function with a regularization term is used to divide the localization problem into two subproblems. An iterative method, whose start-point is obtained by an unconstrained squared-range (USR) algorithm, is then used to obtain a solution. Numerical simulations are carried out to show the effectiveness of the proposed method, compared with the state-of-the-art approaches in different scenarios.

关键词： Fault tolerance Fault tolerant systems approximation algorithms Noise measurement Wireless sensor networks Electronic mail Probability density function Target localization sensor networks Byzantine fault received signal strength (RSS) generalized trust region sub-problem (GTRS) non-line-of-sight (NLOS)

来源：评论

学校读者我要写书评

暂无评论

On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension 17

On Sparse Hitting Sets: From Fair Vertex Cover to Highway Di...

引用

17th International Symposium on Parameterized and Exact Computation, IPEC 2022

作者： Blum, Johannes Disser, Yann Feldmann, Andreas Emil Gupta, Siddharth Zych-Pawlewicz, Anna Universität Konstanz Germany Technische Universität Darmstadt Germany Charles University Prague Czech Republic University of Warwick Coventry United Kingdom University of Warsaw Poland

ISBN: (纸本)9783959772600

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system (V, F, B) with two families F, B of subsets of the universe V . The task is to find a hitting set for F that minimizes the maximum number of elements in any of the sets of B. This generalizes several problems that have been studied in the literature. Our focus is on determining the complexity of some of these special cases of Sparse-HS with respect to the sparseness k, which is the optimum number of hitting set elements in any set of B (i.e., the value of the objective function). For the Sparse Vertex Cover (Sparse-VC) problem, the universe is given by the vertex set V of a graph, and F is its edge set. We prove NP-hardness for sparseness k ≥ 2 and polynomial time solvability for k = 1. We also provide a polynomial-time 2-approximation algorithm for any k. A special case of Sparse-VC is Fair Vertex Cover (Fair-VC), where the family B is given by vertex neighbourhoods. For this problem it was open whether it is FPT (or even XP) parameterized by the sparseness k. We answer this question in the negative, by proving NP-hardness for constant k. We also provide a polynomial-time (2 - k1)-approximation algorithm for Fair-VC, which is better than any approximation algorithm possible for Sparse-VC or the Vertex Cover problem (under the Unique Games Conjecture). We then switch to a different set of problems derived from Sparse-HS related to the highway dimension, which is a graph parameter modelling transportation networks. In recent years a growing literature has shown interesting algorithms for graphs of low highway dimension. To exploit the structure of such graphs, most of them compute solutions to the r-Shortest Path Cover (r-SPC) problem, where r > 0, F contains all shortest paths of length between r and 2r, and B contains all balls of radius 2r. It is known that there is an XP algorithm that computes solutions to r-SPC of sparseness at most h if the input graph has highway dimension

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Kidney Exchange 21

Parameterized Algorithms for Kidney Exchange

引用

21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022

作者： Maiti, Arnab Dey, Palash Indian Institute of Technology Kharagpur Kharagpur India

ISBN: (纸本)9781713854333

In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor;directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most c and p respectively that covers at least some specific number t of non-altruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{p, c}, and (3) the number of vertex types in the input graph when p ≤ c. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange. © 2022 International Foundation for Autonomous Agents and Multiagent Systems (***). All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs 30

Fine-Grained Complexity Lower Bounds for Families of Dynamic...

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Henzinger, Monika Paz, Ami Sricharan, A.R. Department of Computer Science Universität Wien Austria LISN CNRS Paris-Saclay University France

ISBN: (纸本)9783959772471

A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions. Prior work has shown strong conditional lower bounds for general dynamic graphs, yet graph families that arise in practice often exhibit structural properties that the existing lower bound constructions do not possess. We study three specific graph families that are ubiquitous, namely constant-degree graphs, power-law graphs, and expander graphs, and give the first conditional lower bounds for them. Our results show that even when restricting our attention to one of these graph classes, any algorithm for fundamental graph problems such as distance computation or approximation or maximum matching, cannot simultaneously achieve a sub-polynomial update time and query time. For example, we show that the same lower bounds as for general graphs hold for maximum matching and (s, t)-distance in constant-degree graphs, power-law graphs or expanders. Namely, in an m-edge graph, there exists no dynamic algorithms with both O(m1/2-ϵ) update time and O(m1-ϵ) query time, for any small ϵ > 0. Note that for (s, t)-distance the trivial dynamic algorithm achieves an almost matching upper bound of constant update time and O(m) query time. We prove similar bounds for the other graph families and for other fundamental problems such as densest subgraph detection and perfect matching. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

SAT Backdoors: Depth Beats Size 30

SAT Backdoors: Depth Beats Size

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Dreier, Jan Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group University of Leeds United Kingdom

ISBN: (纸本)9783959772471

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. Bounded backdoor size implies bounded backdoor depth, but there are formulas of constant backdoor depth and arbitrarily large backdoor size. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. We base our FPT approximation algorithm on a sophisticated notion of obstructions, extending Mählmann et al.'s obstruction trees in various ways, including the addition of separator obstructions. We develop the algorithm through a new game-theoretic framework that simplifies the reasoning about backdoors. Finally, we show that bounded backdoor depth captures tractable classes of CNF formulas not captured by any known method. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

K-Submodular Cover Problem: Application and algorithms 22

K-Submodular Cover Problem: Application and Algorithms

引用

11th International Symposium on Information and Communication Technology, SoICT 2022

作者： Pham, Phuong N.H. Co, Quy T.N. Su, Anh N. Pham, Phuong T. Pham, Canh V. Snasel, Vaclav Falcuty of Information Technology Ho Chi Minh City University of Food Industry Viet Nam People's Security Academy Viet Nam Ghtk Joint Stock Company Viet Nam Phenikaa University Viet Nam VSB-Technical University of VSB-Technical University of Ostrava Czech Republic

ISBN: (纸本)9781450397254

In this paper, we investigate a novel combinatorial optimization, k-Submodular Cover, as follows: Given a finite set V, a monotone k-submodular function , and a threshold . The problem aim at finding a solution with the size is minimal so that the function . This problem is a general version of the well-known Submodular Cover problem and thus it is NP-hard. Two efficient algorithms for the k-Submodular Cover problem are proposed. The first one is Greedy algorithm and the second one is a Streaming algorithm with theoretical guarantees. Extensive experiments on real-world datasets show that the proposed algorithms are more effective than the state-of-The-Art methods in the application of Influence Threshold with k topics. In particular, our streaming algorithm not only provides a guaranteed theoretical solution, but also proves to be superior to the rest of the algorithms in terms of running time. © 2022 ACM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Delay-Sensitive Energy-Harvesting Wireless Sensors: Optimal Scheduling, Structural Properties, and approximation Analysis

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2020年第4期68卷 2509-2524页

作者： Sharma, Nikhilesh Mastronarde, Nicholas Chakareski, Jacob SUNY Buffalo Dept Elect Engn Buffalo NY 14260 USA New Jersey Inst Technol Coll Comp Newark NJ 07103 USA

We consider an energy harvesting sensor transmitting latency-sensitive data over a fading channel. We aim to find the optimal transmission scheduling policy that minimizes the packet queuing delay given the available harvested energy. We formulate the problem as a Markov decision process (MDP) over a state-space spanned by the transmitter's buffer, battery, and channel states, and analyze the structural properties of the resulting optimal value function, which quantifies the long-run performance of the optimal scheduling policy. We show that the optimal value function (i) is non-decreasing and has increasing differences in the queue backlog;(ii) is non-increasing and has increasing differences in the battery state;and (iii) is submodular in the buffer and battery states. Taking advantage of these structural properties, we derive an approximate value iteration algorithm that provides a controllable tradeoff between approximation accuracy, computational complexity, and memory, and we prove that it converges to a near-optimal value function and policy. Our numerical results confirm these properties and demonstrate that the resulting scheduling policies outperform a greedy policy in terms of queuing delay, buffer overflows, energy efficiency, and sensor outages.

关键词： Sensors Batteries Scheduling Energy harvesting Optimal scheduling approximation algorithms Wireless sensor networks Markov decision processes energy harvesting latency-sensitive wireless sensing approximate dynamic programming structural properties

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：