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

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Chechik, Shiri Zhang, Tianyi Tel Aviv Univ Blavatnik Sch Comp Sci Tel Aviv Israel

ISBN: (纸本)9781665455190

In a weighed directed graph G = (V, E, omega) with m edges and n vertices, we are interested in its basic graph parameters such as diameter, radius and eccentricities, under the nonstandard measure of min-distance which is defined for every pair of vertices u, v is an element of V as the minimum of the shortest path distances from u to v and from v to u. Similar to standard shortest paths distances, computing graph parameters exactly in terms of min-distances essentially requires (Omega) over tilde (mn) time under plausible hardness conjectures. Hence, for faster running time complexities we have to tolerate approximations. Abboud, Vassilevska Williams and Wang [SODA 2016] were the first to study min-distance problems, and they obtained constant factor approximation algorithms in acyclic graphs, with running time (O) over tilde (m) and (O) over tilde (m root n) for diameter and radius, respectively. The time complexity of radius in acyclic graphs was recently improved to (O) over tilde (m) by Dalirrooyfard and Kaufmann [ICALP 2021], but at the cost of an O(log n) approximation ratio. For general graphs, the authors of [DWV+, ICALP 2019] gave the first constant factor approximation algorithm for diameter, radius and eccentricities which runs in time (O) over tilde (m root n);besides, for the diameter problem, the running time can be improved to (O) over tilde (m) while blowing up the approximation ratio to O(log n). A natural question is whether constant approximation and near-linear time can be achieved simultaneously for diameter, radius and eccentricities;so far this is only possible for diameter in the restricted setting of acyclic graphs. In this paper, we answer this question in the affirmative by presenting near-linear time algorithms for all three parameters in general graphs.

关键词： Weight measurement Computer science Costs Directed graphs approximation algorithms Time complexity Standards

来源：评论

学校读者我要写书评

暂无评论

A Parameterized approximation Scheme for Min k-Cut

引用

SIAM JOURNAL ON COMPUTING 2024年第6期53卷 FOCS20-205-FOCS20-238页

作者： Lokshtanov, Daniel Saurabh, Saket Surianarayanan, Vaishali Univ Calif Santa Barbara Santa Barbara CA 93106 USA Inst Math Sci TCS Chennai 600113 Tamil Nadu India

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k, and the task is to partition the vertex set into k nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821-2837] initiated the study of FPT-approximation for the Min k-Cut problem and gave a 1.9997-approximation algorithm running in time 2(O(k6))n(O(1)). Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113-123] designed a (1 + epsilon)-approximation algorithm that runs in time (k/epsilon)(O(k))n(k+O(1)) and a 1.81-approximation algorithm running in time 2(O(k2))n(O(1)). More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990-999] gave a (5/3 + epsilon)-approximation for Min k-Cut running in time 2(O(k2log) (k))n(O(1)). In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every epsilon>0, the algorithm obtains a (1 + epsilon)-approximate solution in time (k/epsilon)(O(k))n(O(1)). The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time s(O(k))n(O(1)) on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The

关键词： MIN k-CUT FPT approximation scheme k-cut sparsifiers approximation algorithms parameterized approximation scheme minimum k-way cuts

来源：评论

学校读者我要写书评

暂无评论

A New Frequency Confined Gramians-based Model Order Reduction Technique

A New Frequency Confined Gramians-based Model Order Reductio...

引用

Australian and New Zealand Control Conference (ANZCC)

作者： Kanchan, Kumari Kumar, Deepak Sreeram, Victor MNNIT Allahabad EED Allahabad India Nalanda Coll Engn EED Gokhulpur Bihar India Univ Western Australia Sch Elect Elect & Comp Engn Crawley WA Australia

ISBN: (纸本)9798350314977

Model order reduction (MOR) is an approach that provides a lower-order system for a given higher-order system. Sometimes, specific frequency restrictions constitute a significant focus for practical applications, such as controller and filter designs that lead to frequency-limited MOR. Gwaronski and Juang were the first to propose a method for frequency-limited MOR. However, this method suffers from instability issues. Hence, this paper presents a new algorithm to overcome the instability issue and provide lower approximation error for the specified frequency range than existing methods. Two numerical examples are included to exhibit the benefits of the suggested approach. An eigenvalue analysis for the reduced-order models is also done to show the stability of the obtained reduced models.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse Fourier transforms on rank-1 lattices for the rapid and low-memory approximation of functions of many variables

引用

SAMPLING THEORY SIGNAL PROCESSING AND DATA ANALYSIS 2022年第1期20卷 1-45页

作者： Gross, Craig Iwen, Mark Kammerer, Lutz Volkmer, Toni Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Math E Lansing MI USA Michigan State Univ Dept Computat Math Sci & Engn CMSE E Lansing MI USA Tech Univ Chemnitz Fac Math Chemnitz Germany

This paper considers fast and provably accurate algorithms for approximating smooth functions on the d-dimensional torus, f:T-d -> C, that are sparse (or compressible) in the multidimensional Fourier basis. In particular, suppose that the Fourier series coefficients of f, {c(k)(f)}k is an element of Z(d), are concentrated in a given arbitrary finite set I subset of Z(d) so that min(Omega subset of I s.t. |Omega|=s)||f-Sigma(k is an element of Omega) c(k)(f)e(-2 pi ik center dot circle)||(2)algorithms for solving this problem using O(s(2)dlog(c)(|I|))-time/memory and O(sdlog(c)(|I|))-time/memory, respectively. Most crucially, all of the methods proposed herein achieve these runtimes while simultaneously satisfying theoretical best s-term approximation guarantees which guarantee their numerical accuracy and robustness to noise for general functions. These results are achieved by modifying several different one-dimensional Sparse Fourier Transform (SFT) methods to subsample a function along a reconstructing rank-1 lattice for the given frequency set f subset of Z(d) in order to rapidly identify a near-minimizing subset Omega subset of f as above without having to use anything about the lattice beyond its generating vector. This requires the development of new fast and low-memory frequency identification techniques capable of rapidly recovering vector-valued frequencies in Z(d) as opposed to recovering simple integer frequencies as required in the univariate setting. Two different multivariate frequency identification strategies are proposed, analyzed, and shown to lead to their own best s-term approximation methods h

关键词： Multivariate Fourier approximation approximation algorithms Fast Fourier transforms Sparse Fourier transforms Rank-1 lattices Fast algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards Distributed 2-approximation Steiner Minimal Trees in Billion-edge Graphs 36

Towards Distributed 2-Approximation Steiner Minimal Trees in...

引用

36th IEEE International Parallel and Distributed Processing Symposium (IEEE IPDPS)

作者： Reza, Tahsin Sanders, Geoffrey Pearce, Roger Lawrence Livermore Natl Lab LLNL Ctr Appl Sci Comp CASC Livermore CA 94550 USA

ISBN: (纸本)9781665481069

Given an edge-weighted graph and a set of known seed vertices of interest, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. If the size of the seed set is 2, shortest path calculations are an attractive computational kernel to explore the connections between the two vertices. When the seed set is 3 or larger (say up to 1,000s) Steiner minimal tree - min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices - is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but decades ago several polynomial-time algorithms were designed and proven to yield Steiner trees whose total weight is bounded within 2 times the minimal Steiner tree. Despite its rich theoretical literature, works related to parallel Steiner minimal tree computation and their scalable implementations are rather scarce. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm (with theoretical guarantees) and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many approximation algorithms, the solution we employ, exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, employs techniques to avoid inefficient distributed spanning tree computation on the entire graph, and harnesses a combination of vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance of our solution using real-world graphs with up to 128 billion edges and 512 compute nodes (8K processes), show the ability to find Steiner trees with up to 10K seed ver

关键词： Steiner trees Distributed processing Scalability approximation algorithms Computational efficiency Kernel Convergence

来源：评论

学校读者我要写书评

暂无评论

A 40nm 5.6TOPS/W 239GOPS/mm² Self-Attention Processor with Sign Random Projection-based approximation 48

A 40nm 5.6TOPS/W 239GOPS/mm<SUP>2</SUP> Self-Attention Proce...

引用

48th IEEE European Solid State Circuits Conference (ESSCIRC)

作者： Seo, Seong Hoon Kim, Soosung Jung, Sung Jun Kwon, Sangwoo Lee, Hyunseung Lee, Jae W. Seoul Natl Univ Seoul 08826 South Korea

ISBN: (数字)9781665484947

ISBN: (纸本)9781665484947

Transformer architecture is one of the most remarkable recent breakthroughs in neural networks, achieving state-of-the-art (SOTA) performance on various natural language processing (NIP) and computer vision tasks. Self-attention is the key enabling operation for transformer-based models. However, its quadratic computational complexity to the sequence length makes this operation the major performance bottleneck for those models. Thus, we propose a novel self-attention accelerator that skips most of the computation by utilizing an approximate candidate selection algorithm. Implemented in a 40nm CMOS technology, our 5.64 mm(2) chip operates at 100-600 MHz consuming 483-685 mW to achieve the energy and area efficiency of 0.354-5.61 TOPS/W and 239 GOPS/mm(2), respectively.

关键词： Semiconductor device modeling Computer vision Computational modeling Neural networks Europe Transformers approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Resilient approximation-Based Distributed Nonconvex Optimization

Resilient Approximation-Based Distributed Nonconvex Optimiza...

引用

American Control Conference (ACC)

作者： Zhang, Yilin He, Zhiyu He, Jianping Shanghai Jiao Tong Univ Dept Automat Key Lab Syst Control & Informat Proc Minist Educ China Shanghai 200240 Peoples R China Shanghai Engn Res Ctr Intelligent Control & Manag Shanghai 200240 Peoples R China

ISBN: (数字)9781665451963

ISBN: (纸本)9781665451963

There has been an approximation-based distributed optimization algorithm that solves univariate nonconvex problems to arbitrary precision. The key idea is to construct approximations of local objectives and address a more structured approximate version of the problem. By representing diverse local objectives with compressed coefficients vectors, such algorithms enjoy gradient-free iterations but face severe security issues when adversaries occur. In this paper, we propose a resilient approximation-based distributed nonconvex optimization algorithm termed R-ADOA to defend attacks from malicious nodes. First, errors caused by adversaries are quantified and unified as the perturbation of coefficient vectors of approximations. Next, we propose a filtering mechanism and resilient stopping mechanism to limit errors arising in consensus-based iterations. Finally, an upper bound of the deviations of the obtained solutions from optimal solutions is given based on the eigenvalue perturbation theory of matrices. Numerical experiments are provided to illustrate the effectiveness of our algorithm. Compared to existing resilient distributed optimization algorithms, R-ADOA addresses nonconvex problems, converges exponentially fast, and contains explicit bounds for the deviations of solutions.

关键词： Upper bound Filtering Sensitivity analysis Perturbation methods approximation algorithms Linear programming Robustness

来源：评论

学校读者我要写书评

暂无评论

Fully Dynamic k-Center in Low Dimensions via Approximate Furthest Neighbors 7

Fully Dynamic k-Center in Low Dimensions via Approximate Fur...

引用

Symposium on Simplicity in algorithms (SOSA)

作者： Gant, Jinxiang Golin, Mordecai J. Hong Kong UST CSE Dept Hong Kong Peoples R China

ISBN: (纸本)9781611977936

Given a set of points P, the k-center problem is to find a minimum radius r* and associated center set of k points C such that the distance from each point in P to its closest center is at most r*. While this problem is NP-hard to solve, there exists a famous O(kn) time 2-approximation algorithm due to Gonzalez. This works by repeatedly adding the furthest neighbor in P to the current center set C until C contains exactly k centers. The dynamic version of the problem is to maintain P over insertions and deletions of points, in a way that permits efficiently solving the k center problem for the current P. There are various specialized (2 + epsilon)-approximation algorithms for solving this. Another dynamic problem, which does not seem to have been previously studied, is how to dynamically maintain a set of points P so as to efficiently solve the approximate furthest neighbor problem i.e., given a second point set C ', to find a point p is an element of P that is a (1 + epsilon) approximate furthest neighbor from C '. We show that, for points in bounded doubling dimension, the approximate furthest neighbor problem can be solved using the known navigating nets data structure in new way. This immediately provides a new algorithm for solving the dynamic k-center problem by replacing the search for a furthest neighbor in P to C in Gonzalez's algorithm with an approximate furthest neighbor search. Unlike some of the older algorithms, this new approach does not require knowing k or epsilon in advance. This new approach can also be used to solve the dynamic Euclidean k-center problem.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Strategies for Compressing the Pareto Frontier: Application to Strategic Planning of Hydropower in the Amazon Basin 1

引用

21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Qu, Zhongdi Grimson, Marc Mao, Yue Heilpern, Sebastian Miqueleiz, Imanol Pacheco, Felipe Flecker, Alexander Gomes, Carla P. Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Cornell Univ Dept Ecol & Evolutionary Biol Ithaca NY USA

ISBN: (数字)9783031605994

ISBN: (纸本)9783031606014;9783031605994

The development of ethical AI decision-making systems requires considering multiple criteria, often resulting in a large spectrum of partially ordered solutions. At the core of this challenge lies the Pareto frontier, the set of all feasible solutions where no solution is dominated by another. In previous work, we developed both exact and approximate algorithms for generating the Pareto frontier for tree-structured networks. However, as the number of criteria grows, the Pareto frontier increases exponentially, posing a significant challenge for decision-makers. To address this challenge, we propose various strategies to efficiently compress the Pareto frontier, including an approximation method with optimality and polynomial runtime guarantees. We provide detailed empirical results on the strategies' effectiveness in the context of strategic planning of the hydropower expansion in the Amazon basin. Our strategies offer a more manageable approach for navigating Pareto frontiers.

关键词： Multi-objective optimization approximation algorithms Hierarchical clustering

来源：评论

学校读者我要写书评

暂无评论

Eigencontours: Novel Contour Descriptors Based on Low-Rank approximation

Eigencontours: Novel Contour Descriptors Based on Low-Rank A...

引用

IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)

作者： Park, Wonhui Jin, Dongkwon Kim, Chang-Su Korea Univ Seoul South Korea

ISBN: (数字)9781665469463

ISBN: (纸本)9781665469463

Novel contour descriptors, called eigencontours, based on low-rank approximation are proposed in this paper. First, we construct a contour matrix containing all object boundaries in a training set. Second, we decompose the contour matrix into eigencontours via the best rank-M approximation. Third, we represent an object boundary by a linear combination of the Al eigencontours. We also incorporate the eigencontours into an instance segmentation framework. Experimental results demonstrate that the proposed eigencontours can represent object boundaries more effectively and more e f ficiently than existing descriptors in a low-dimensional space. Furthermore, the proposed algorithm yields meaningfid performances on instance segmentation datasets.

关键词： Training Computer vision approximation algorithms Pattern recognition Matrix decomposition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：