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

Covering rectilinear polygons with axis-parallel rectangles

SIAM JOURNAL ON COMPUTING 2003年第6期32卷 1509-1541页

作者： Kumar, VSA Ramesh, H Los Alamos Natl Lab Los Alamos NM 87544 USA Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

We give an O(root log n) factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an ... 详细信息

关键词： approximation algorithms covering polygons

来源：评论

学校读者我要写书评

暂无评论

CONJUGACY ANALYSIS OF THE FINITE-DIFFERENCE EQUATIONS OF THE METHOD OF CHARACTERISTICS ON THE BASIS OF A LINEAR-ALGEBRAIC FORMULATION

引用

ATOMIC ENERGY 2017年第6期122卷 369-376页

作者： Suslov, I. R. Tormyshev, I. V. Russian Federat Leipunskii Inst Phys & Power Engn State Sci Ctr Obninsk Russia

A linear-algebraic form of the equations of the method of characteristics, which is used to approximate the neutron transport equation, is obtained. It is shown on the basis of the obtained linear-algebraic form that the discrete form of the conjugate equation differs from the algebraically discrete problem constructed by linear-algebraic transformations of the discrete form of the normal problem. The reason for the discrepancy lies in the approximation of the volumes of the spatial cells in covering the working region by a network of characteristics. It is shown by means of test calculations that when the network of characteristics is refined the solution of the conjugate transport equation converges to the solution of the algebraically conjugate problem.

关键词： FINITE difference method LINEAR algebraic groups NEUTRON transport theory approximation algorithms TRANSPORT theory (Mathematics)

来源：评论

学校读者我要写书评

暂无评论

Dual Heuristic Programming for Optimal Control of Continuous-Time Nonlinear Systems Using Single Echo State Network

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第3期52卷 1701-1712页

作者： Liu, Chong Zhang, Huaguang Luo, Yanhong Su, Hanguang Northeastern Univ Sch Informat Sci & Engn Shenyang 110004 Peoples R China Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110004 Peoples R China

This article presents an improved online adaptive dynamic programming (ADP) algorithm to solve the optimal control problem of continuous-time nonlinear systems with infinite horizon cost. The Hamilton-Jacobi-Bellman (HJB) equation is iteratively approximated by a novel critic-only structure which is constructed using the single echo state network (ESN). Inspired by the dual heuristic programming (DHP) technique, ESN is designed to approximate the costate function, then to derive the optimal controller. As the ESN is characterized by the echo state property (ESP), it is proved that the ESN can successfully approximate the solution to the HJB equation. Besides, to eliminate the requirement for the initial admissible control, a new weight tuning law is designed by adding an alternative condition. The stability of the closed-loop optimal control system and the convergence of the out weights of the ESN are guaranteed by using the Lyapunov theorem in the sense of uniformly ultimately bounded (UUB). Two simulation examples, including linear system and nonlinear system, are given to illustrate the availability and effectiveness of the proposed approach by comparing it with the polynomial neural-network scheme.

关键词： Optimal control approximation algorithms Artificial neural networks Nonlinear systems Tuning Convergence Stability analysis Adaptive dynamic programming (ADP) echo state network (ESN) Hamilton-Jacobi-Bellman (HJB) nonlinear systems optimal control

来源：评论

学校读者我要写书评

暂无评论

Cost-Aware and Distance-Constrained Collective Spatial Keyword Query

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第2期35卷 1324-1336页

作者： Chan, Harry Kai-Ho Liu, Shengxin Long, Cheng Wong, Raymond Chi-Wing Roskilde Univ Dept People & Technol Roskilde 4000 Denmark Harbin Inst Technol Sch Comp Sci & Technol Shenzhen 518055 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China

With the proliferation of location-based services, geo-textual data is becoming ubiquitous. Objects involved in geo-textual data include geospatial locations, textual descriptions or keywords, and various attributes (e.g., a point-of-interest has its expenses and users' ratings). Many types of spatial keyword queries have been proposed on geo-textual data. Among them, one prominent type is to find, for a query consisting of a query location and some query keywords, a set of multiple objects such that the objects in the set collectively cover all the query keywords and the object set is of good quality according to some criteria. Existing studies define the criteria either based on the geospatial information of the objects solely or simply treat the geospatial information and the attribute information of the objects together without differentiation though they may have different semantics and scales. As a result, they cannot provide users flexibility to express finer grained preferences on the objects. In this paper, we propose a new criterion which is to find a set of objects where the distance (defined based on the geospatial information) is at most a threshold specified by users and the cost (defined based on the attribute information) is optimized. We develop a suite of two algorithms including an exact algorithm and an approximation algorithm with provable guarantees for the problem. We conducted extensive experiments on real datasets which verified the efficiency and effectiveness of proposed algorithms.

关键词： Geospatial analysis approximation algorithms Semantics Cost function Spatial databases Search problems Mice Spatial keyword queries spatial database query processing

来源：评论

学校读者我要写书评

暂无评论

Signed genome rearrangement by reversals and transpositions: models and approximations

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期259卷 513-531页

作者： Lin, GH Xue, GL Univ Vermont Dept Comp Sci Burlington VT 05405 USA

An important problem in computational biology is the genome rearrangement using reversals and transpositions. Analysis of genome evolving by reversals and transpositions leads to a combinatorial optimization problem of sorting by reversals and transpositions, i.e., sorting of a pen-nutation using reversals and transpositions of arbitrary fragments. The reversal operation works on a single segment of the genome by reversing the selected segment. Two kinds of transpositions have been studied in the literature. The first kind of transposition operations delete a segment of the genome and insert it into another position in the genome. The second kind of transposition operations delete a segment of the genome and insert its inverse into another position in the genome. Both transposition operations can be viewed as operations working on two consecutive segments. In this payer, we introduce a third transposition operation which works on two consecutive segments and study sorting of a signed permutation by reversals and transpositions. By allowing reversals and the first kind of transpositions, or reversals and the first two kinds of transpositions, or reversals and all three kinds of transpositions, we have three problem models. After establishing a common lower bound on the number of operations needed, we present a unified 2-approximation algorithm for all these problems. Finally, we present a better 1.75-approximation for the third problem. (C) 2001 Published by Elsevier Science B.V.

关键词： approximation algorithms genome rearrangement sorting of permutations

来源：评论

学校读者我要写书评

暂无评论

Minimum Hitting Set of Interval Bundles Problem: Computational Complexity and Approximability

引用

ALGORITHMICA 2022年第8期84卷 2222-2239页

作者： Gottschau, Marinus Leichter, Marilena Tech Univ Munich Dept Math Operat Res Munich Germany

The minimum hitting set of bundles problem (Mhsb) is a natural generalization of the minimum hitting set problem, where instead of hitting single elements, bundles of elements are hit. More specifically, we are given a ground set of elements and a family of sets. Every set in this family contains bundles of elements, which are subsets of the ground set. The task is to find a collection of elements of minimum size such that at least one bundle of every set in the family is hit. Motivated by several applications, we consider Mhsb restricted to interval and 2-dimensional interval bundles. We study the computational complexity and give polynomial-time algorithms for several classes of instances with these special structured bundles.

关键词： Hitting set approximation algorithms Maintenance scheduling

来源：评论

学校读者我要写书评

暂无评论

Safe Off-Policy Deep Reinforcement Learning Algorithm for Volt-VAR Control in Power Distribution Systems

引用

IEEE TRANSACTIONS ON SMART GRID 2020年第4期11卷 3008-3018页

作者： Wang, Wei Yu, Nanpeng Gao, Yuanqi Shi, Jie Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

Volt-VAR control is critical to keeping distribution network voltages within allowable range, minimizing losses, and reducing wear and tear of voltage regulating devices. To deal with incomplete and inaccurate distribution network models, we propose a safe off-policy deep reinforcement learning algorithm to solve Volt-VAR control problems in a model-free manner. The Volt-VAR control problem is formulated as a constrained Markov decision process with discrete action space, and solved by our proposed constrained soft actor-critic algorithm. Our proposed reinforcement learning algorithm achieves scalability, sample efficiency, and constraint satisfaction by synergistically combining the merits of the maximum-entropy framework, the method of multiplier, a device-decoupled neural network structure, and an ordinal encoding scheme. Comprehensive numerical studies with the IEEE distribution test feeders show that our proposed algorithm outperforms the existing reinforcement learning algorithms and conventional optimization-based approaches on a large feeder.

关键词： Voltage control Reinforcement learning approximation algorithms Distribution networks Aerospace electronics Switches Deep reinforcement learning model-free off-policy safe reinforcement learning Volt-VAR control

来源：评论

学校读者我要写书评

暂无评论

All-pairs almost shortest paths

引用

SIAM JOURNAL ON COMPUTING 2000年第5期29卷 1740-1759页

作者： Dor, D Halperin, S Zwick, U Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

Let G = (V, E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth et al. [SIAM J. Comput., 28 (1999), pp. 1167 1181], we describe an (O) over tilde(min{n(3/2)m(1/2),n(7/3)})-time algorithm APASP(2) for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP(2) is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k > 2, we describe an (O) over tilde(min{n(2-2/(k+2))m(2/(k+2)),n(2+2/(3k-2))})-time algorithm APASP(k) for computing all distances in G with an additive one-sided error of at most k. We also give an (O) over tilde(n(2))-time algorithm APASP(infinity) for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in (O) over tilde(n(2)) time. We say that a weighted graph F = (V, E') k-emulates an unweighted graph G = (V, E) if for every u, v is an element of V we have delta(G)(u, v) less than or equal to delta(F)(u, v) less than or equal to delta(G)(u, v) + k. We show that every unweighted graph on n vertices has a 2-emulator with (O) over tilde(n(3/2)) edges and a 4-emulator with (O) over tilde(n(4/3)) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with (O) over tilde(n(3/2)) edges and that such a 3-spanner can be built in (O) over tilde(mn(1/2)) time. We also describe an (O) over tilde(n(m(2/3)+n))-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.

关键词： graph algorithms shortest paths approximation algorithms spanners emulators

来源：评论

学校读者我要写书评

暂无评论

Improving Effectiveness of Simulation-Based Inference in the Massively Parallel Regime

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2023年第4期34卷 1100-1114页

作者： Kulkarni, Sourabh Moritz, Csaba Andras Univ Massachusetts Dept Elect & Comp Engn Amherst MA 01003 USA

Simulation-based Inference (SBI) is a widely used set of algorithms to learn the parameters of complex scientific simulation models. While primarily run on CPUs in High-Performance Compute clusters, these algorithms have been shown to scale in performance when developed to be run on massively parallel architectures such as GPUs. While parallelizing existing SBI algorithms provides us with performance gains, this might not be the most efficient way to utilize the achieved parallelism. This work proposes a new parallelism-aware adaptation of an existing SBI method, namely approximate Bayesian computation with Sequential Monte Carlo(ABC-SMC). This new adaptation is designed to utilize the parallelism not only for performance gain, but also toward qualitative benefits in the learnt parameters. The key idea is to replace the notion of a single 'step-size' hyperparameter, which governs how the state space of parameters is explored during learning, with step-sizes sampled from a tuned Beta distribution. This allows this new ABC-SMC algorithm to more efficiently explore the state-space of the parameters being learned. We test the effectiveness of the proposed algorithm to learn parameters for an epidemiology model running on a Tesla T4 GPU. Compared to the parallelized state-of-the-art SBI algorithm, we get similar quality results in similar to 100x fewer simulations and observe similar to 80x lower run-to-run variance across 10 independent trials.

关键词： Inference algorithms Computational modeling Biological system modeling approximation algorithms Perturbation methods Optimization Bayes methods Approximate Bayesian computation Bayesian inference COVID-19 compartmental models epidemiology GPU high performance computing likelihood-free inference parallel algorithms simulation-based inference statistical machine learning stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

Ultra-Scalable Spectral Clustering and Ensemble Clustering

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2020年第6期32卷 1212-1226页

作者： Huang, Dong Wang, Chang-Dong Wu, Jian-Sheng Lai, Jian-Huang Kwoh, Chee-Keong South China Agr Univ Coll Math & Informat Guangzhou 510640 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510006 Peoples R China Guangdong Key Lab Informat Secur Technol Guangzhou 510006 Peoples R China Minist Educ Key Lab Machine Intelligence & Adv Comp Guangzhou Peoples R China Nanchang Univ Sch Informat Engn Nanchang 330031 Jiangxi Peoples R China

This paper focuses on scalability and robustness of spectral clustering for extremely large-scale datasets with limited resources. Two novel algorithms are proposed, namely, ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for $K$K-nearest representatives are proposed for the construction of a sparse affinity sub-matrix. By interpreting the sparse sub-matrix as a bipartite graph, the transfer cut is then utilized to efficiently partition the graph and obtain the clustering result. In U-SENC, multiple U-SPEC clusterers are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC while maintaining high efficiency. Based on the ensemble generation via multiple U-SEPC's, a new bipartite graph is constructed between objects and base clusters and then efficiently partitioned to achieve the consensus clustering result. It is noteworthy that both U-SPEC and U-SENC have nearly linear time and space complexity, and are capable of robustly and efficiently partitioning 10-million-level nonlinearly-separable datasets on a PC with 64 GB memory. Experiments on various large-scale datasets have demonstrated the scalability and robustness of our algorithms. The MATLAB code and experimental data are available at https://***/publication/330760669.

关键词： Clustering algorithms Sparse matrices Complexity theory Robustness Bipartite graph Scalability approximation algorithms Data clustering large-scale clustering spectral clustering ensemble clustering large-scale datasets nonlinearly separable datasets

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：