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

THEORETICAL COMPUTER SCIENCE 2010年第40-42期411卷 3701-3713页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Dept Math Comp Sci & Mech PL-02097 Warsaw Poland

In this paper we gather several improvements in the field of exact and approximate exponential time algorithms for the BANDWIDTH problem. For graphs with treewidth t we present an O(n(0(t))2(n)) exact algorithm. Moreover, for any two positive integers k >= 2, r >= 1, we present a (2kr - 1)-approximation algorithm that solves BANDWIDTH for an arbitrary input graph in O*(k(n/(k-1)r)) time and polynomial space where by O* we denote the standard big O notation but omitting polynomial factors. Finally, we improve the currently best known exact algorithm for arbitrary graphs with an O(4.383(n)) time and space algorithm. In the algorithms for the small treewidth we develop a technique based on the Fast Fourier Transform, parallel to the Fast Subset Convolution techniques introduced by Bjorklund et al. This technique can be also used as a simple method of finding a chromatic number of all subgraphs of a given graph in O*(2(n)) time and space, what matches the best known results. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bandwidth Exponential algorithm Exact algorithm approximate algorithm Graph

来源：评论

学校读者我要写书评

暂无评论

An approximate approach to belief revision

引用

LOGIC JOURNAL OF THE IGPL 2012年第2期20卷 486-496页

作者： Luan, Shangmin Dai, Guozhong Magnani, Lorenzo Chinese Acad Sci Inst Software Beijing Peoples R China Univ Pavia Dept Philosophy I-27100 Pavia Italy

It is well known that the computational complexity of propositional knowledge base revision is at the second level of polynomial hierarchy. A way to solve this kind of problems is to introduce approximate algorithms. In this paper, an approximate approach is introduced for belief change. Operators, which satisfy the AGM rational postulates, are defined to change belief sets or belief bases. Furthermore, approximate algorithms to implement the revision of finite belief bases are presented. The time complexities of the approximate algorithms shown in this paper are at lower level than the time complexities of the existed approaches in literatures, although they may not generate the optimal solution, and this is meaningful from the theoretical point of view.

关键词： Belief revision approximate algorithm integrity constraints finite belief base

来源：评论

学校读者我要写书评

暂无评论

FABLE: approximate Butterfly Counting in Bipartite Graph Stream with Duplicate Edges 24

FABLE: Approximate Butterfly Counting in Bipartite Graph Str...

引用

33rd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Sun, Guozhang Zhao, Yuhai Li, Yuan Northeastern Univ Shenyang Peoples R China North China Univ Technol Beijing Peoples R China

ISBN: (纸本)9798400704369

Bipartite graph models the relationship between two different sets of entities. Such graph data become more dynamic and are organized as stream with duplicate edges in real-word applications such as customer-product in e-commerce. A butterfly, (2,2)-biclique, is the simplest cohesive substructure and of great importance in a bipartite graph. However, it is challenging to estimate the number of butterflies in large scale and high dynamic bipartite graph stream when given a limited memory. Besides, existing works for butterfly counting assume no duplicate edges in the bipartite graph stream, which cause less accuracy in bipartite graph stream with duplicate edges. In this paper, we propose FABLE, a Fixed-size memory approximate Butterfly counting algorithm for dupLicate Edges in bipartite graph stream. In FABLE, we compute the number of distinct edges by maintaining an ordered list of edge priorities for replacement and sampling. We provide theoretical proof of unbiasedness and derive the variance of butterfly count. Our extensive experiments on 5 real-world datasets confirm that our approach has higher accuracy compared with the baseline method under the same memory usage.

关键词： Bipartite Graph Stream Butterfly Counting approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast approximate All Pairwise CoSimRanks via Random Projection 22nd

Fast Approximate All Pairwise CoSimRanks via Random Projecti...

引用

22nd International Conference on Web Information Systems Engineering (WISE)

作者： Yang, Renchi Xiao, Xiaokui Natl Univ Singapore Singapore Singapore

ISBN: (纸本)9783030908881;9783030908874

Given a graph G with n nodes, and two nodes u, v is an element of G, the CoSimRank value s(u, v) quantifies the similarity between u and v based on graph topology. Compared to SimRank, CoSimRank is shown to be more accurate and effective in many real-world applications including synonym expansion, lexicon extraction, and entity relatedness in knowledge graphs. The computation of all pairwise CoSimRanks in G is highly expensive and challenging. Existing solutions all focus on devising approximate algorithms for the computation of all pairwise CoSimRanks. To attain a desired absolute accuracy guarantee epsilon, the state-of-the-art approximate algorithm for computing all pairwise CoSimRanks requires O(n(3) log(2)(ln(1/epsilon))) time, which is prohibitively expensive even epsilon is large. In this paper, we propose RPCS, a fast randomized algorithm for computing all pairwise CoSimRank values. The basic idea of RPCS is to approximate the n x n matrix multiplications in CoSimRank computation via random projection. Theoretically, RPCS runs in O(n(2) ln(n)/epsilon(2) ln(1/epsilon)) time and meanwhile ensures an absolute error of at most epsilon in each CoSimRank value in G with a high probability. Extensive experiments using six real graphs demonstrate that RPCS is more than up to orders of magnitude faster than the state of the art. In particular, on a million-edge Twitter graph, RPCS answers the epsilon-approximate (epsilon = 0.1) all pairwise CoSimRank query within 4 h, using a single commodity server, while existing solutions fail to terminate within a day.

关键词： CoSimRank Random projection approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximate approach to frequent itemset mining 2

An approximate approach to frequent itemset mining

引用

2nd IEEE International Conference on Data Science in Cyberspace (DSC)

作者： Zhang, Chunkai Zhang, Xudong Tian, Panbo Harbin Inst Technol Shenzhen Grad Sch Dept Comp Sci & Technol Shenzhen Peoples R China

ISBN: (纸本)9781538616000

Eclat algorithm is one of the most widely used frequent itemset mining methods. One significant bottleneck of the Eclat algorithm is that the efficiency for calculating the intersection of itemsets is low especially when the itemsets have a large number of transactions. In this work, for the purpose of efficiency improvement and resource saving, we propose an approximate variation of Eclat algorithm which is based on MinHash technique. A recent research shows that MinHash technique can be used for estimating the size of the intersection of sets. So we investigate the role of MinHash technique to overcome the drawback which inefficiency of itemsets intersection in Eclat algorithm. This approach can provide an approximate answer which is more useful than 'exact' result in many situations. In this work, we propose an approximate algorithm called HashEclat. Our algorithm considers the tradeoff between accuracy of the mining results and algorithm execution time. Both of theoretical analysis and realistic experiments show that it can output almost all the frequent itemsets with faster speed and less memory space. Besides other optimization methods of the Eclat algorithm can also be used in our algorithm, since our method only accelerates calculating the intersection speed.

关键词： frequent itemset approximate algorithm MinHash Eclat

来源：评论

学校读者我要写书评

暂无评论

Fast Instance Search Based on approximate Bichromatic Reverse Nearest Neighbor Search 14

Fast Instance Search Based on Approximate Bichromatic Revers...

引用

ACM Conference on Multimedia (MM)

作者： Iwamura, Masakazu Matozaki, Nobuaki Kise, Koichi Osaka Prefecture Univ Grad Sch Engn Naka Ku 1-1 Gakuencho Sakai Osaka 5998531 Japan

ISBN: (纸本)9781450330633

In the TRECVID Instance Search (INS) task, it is known that use of BM25, which is an improvement of the TFIDF, greatly improves retrieval performance. Its calculation, however, requires tremendous amount of computational cost and this fact makes its use intractable. In this paper, we present its efficient computational method. Since the BM25 is obtained by solving the bichromatic reverse nearest neighbor (BRNN) search problem, we propose an approximate method for the problem based on the state-of-the-art approximate nearest neighbor search method, bucket distance hashing (BDH). An experiment using the TRECVID INS 2012 dataset showed that the proposed method reduced computational cost to less than 1/3500 of the brute-force search with keeping the accuracy.

关键词： Bichromatic reverse nearest neighbor search approximate algorithm Video retrieval BM25 TFIDF

来源：评论

学校读者我要写书评

暂无评论

Addressing the Hardness of k-Facility Relocation Problem: A Pair of approximate Solutions 21

Addressing the Hardness of k-Facility Relocation Problem: A ...

引用

30th ACM International Conference on Information and Knowledge Management (CIKM)

作者： Wang, Hu Li, Hui Wang, Meng Cui, Jiangtao Xidian Univ Xian Peoples R China Xian Polytech Univ Xian Peoples R China

ISBN: (纸本)9781450384469

Facility Relocation (FR), which is an effort to reallocate the placement of facilities to adapt to the changes of urban planning and population distribution, has remarkable impact on many application areas. Existing solutions to the FR problem either focus on relocating one facility (i.e., 1-FR) or fail to guarantee the result quality on relocating k > 1 facilities (i.e., k-FR). As k-FR problem is NP-hard and is not submodular or non-decreasing, traditional hill-climb approximate algorithm cannot be directly applied. In light of that, we propose to transform k-FR into another facility placement problem, which is submodular and non-decreasing. We theoretically prove that the optimal solution of both problems are equivalent. Accordingly, we are able to present the first approximate solution towards the k-FR, namely FR2FP. Our extensive comparison over both FR2FP and the state-of-the-art heuristic solution shows that FR2FP, although provides approximation guarantee, cannot necessarily given superior results to the heuristic solution. The comparison motivates and, more importantly, directs us to present an advanced approximate solution, namely FR2FP-ex. Extensive experimental study over both real-world and synthetic datasets have verified that, FR2FP-ex demonstrates the best result quality. In addition, we also exactly unveil the scenarios when the state-of-the-art heuristic would fail to provide satisfied results in practice.

关键词： Facility Relocation Submodular approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximate Calculation for Error Spectrum

An Approximate Calculation for Error Spectrum

引用

International Conference on Estimation Detection and Information Fusion ICEDIF

作者： Peng, Weishi Fang, Yangwang Chen, Shaohua Air Force Engn Univ Sch Aeronaut & Astronaut Engn Xian 710038 Shaanxi Peoples R China

ISBN: (纸本)9781479964185

As a comprehensive measure, the error spectrum will be widely used for estimation performance evaluation. However, it's hard to calculate without the error distribution. An approximate algorithm is proposed in this study to solve this problem. Then, how the approximate calculation can be used is illustrated by numerical examples. Finally, the correctness of the algorithm is validated by the simulation results.

关键词： error spectrum estimation performance evaluation approximate algorithm the law of large numbers

来源：评论

学校读者我要写书评

暂无评论

Time-frequency analysis of Li solid-phase diffusion in spherical active particles under typical discharge modes

引用

Journal of Energy Chemistry 2022年第4期31卷 209-224页

作者： Qiu-An Huang Yuxuan Bai Liang Wang Juan Wang Fangzhou Zhang Linlin Wang Xifei Li Jiujun Zhang Institute for Sustainable Energy/College of Science Shanghai UniversityShanghai 201800China Shaanxi Key Laboratory of Nanomaterials and Nanotechnology School of Mechanical and Electrical EngineeringXi’an University of Architecture and TechnologyXi’an 710055ShaanxiChina Institute of Materials/School of Materials Science and Engineering Shanghai UniversityShanghai 200072China Xi’an Key Laboratory of New Energy Materials and Devices Institute of Advanced Electrochemical Energy&School of Materials Science and EngineeringXi’an University of TechnologyXi’anShaanxi 710048China

Li transient concentration distribution in spherical active material particles can affect the maximum power density and the safe operating regime of the electric vehicles(EVs). On one hand, the quasiexact/exact solution obtained in the time/frequency domain is time-consuming and just as a reference value for approximate solutions;on the other hand, calculation errors and application range of approximate solutions not only rely on approximate algorithms but also on discharge modes. For the purpose to track the transient dynamics for Li solid-phase diffusion in spherical active particles with a tolerable error range and for a wide applicable range, it is necessary to choose optimal approximate algorithms in terms of discharge modes and the nature of active material particles. In this study, approximation methods,such as diffusion length method, polynomial profile approximation method, Padé approximation method,pseudo steady state method, eigenfunction-based Galerkin collocation method, and separation of variables method for solving Li solid-phase diffusion in spherical active particles are compared from calculation fundamentals to algorithm implementation. Furthermore, these approximate solutions are quantitatively compared to the quasi-exact/exact solution in the time/frequency domain under typical discharge modes, i.e., start-up, slow-down, and speed-up. The results obtained from the viewpoint of time-frequency analysis offer a theoretical foundation on how to track Li transient concentration profile in spherical active particles with a high precision and for a wide application range. In turn, optimal solutions of Li solid diffusion equations for spherical active particles can improve the reliability in predicting safe operating regime and estimating maximum power for automotive batteries.

关键词： Li solid-phase diffusion Discharge mode approximate algorithm Quasi-exact/exact solution Time-frequency analysis

来源：评论

学校读者我要写书评

暂无评论

FlowTrust： trust inference with network flows

引用

Frontiers of Computer Science 2011年第2期5卷 181-194页

作者： Guojun WANG Jie WU School of Information Science and Engineering Central South University Changsha 410083 China Department of Computer and Information Sciences Temple University Philadelphia PA 19122 USA

Web-based social networking is increasingly gaining popularity due to the rapid development of computer networking technologies. However, social networking applications still cannot obtain a wider acceptance by many users due to some unresolved issues, such as trust, security, and privacy. In social networks, trust is mainly studied whether a remote user behaves as expected by an interested user via other users, who are respectively named trustee, trustor, and recommenders. A trust graph consists of a trustor, a trustee, some recommenders, and the trust relationships between them. In this paper, we propose a novel FlowTrust approach to model a trust graph with network flows, and evaluate the maximum amount of trust that can flow through a trust graph using network flow theory. FlowTrust supports multi-dimensional trust. We use trust value and confidence level as two trust factors. We deduce four trust metrics from these two trust factors, which are maximum flow of trust value, maximum flow of confidence level, minimum cost of uncertainty with maximum flow of trust, and minimum cost of mistrust with maximum flow of confidence. We also propose three FlowTrust algorithms to normalize these four trust metrics. We compare our proposed FlowTrust approach with the existing RelTrust and CircuitTrust approaches. We show that all three approaches are comparable in terms of the inferred trust values. Therefore, FlowTrust is the best of the three since it also supports multi-dimensional trust.

关键词： trust inference multi-dimensional trust approximate algorithm network flows social networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：