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

PARALLEL SOLUTION OF CERTAIN TOEPLITZ LINEAR-SYSTEMS

SIAM JOURNAL ON COMPUTING 1984年第2期13卷 268-276页

作者： BINI, D Univ di Pisa Dipartimento di Matematica Pisa Italy Univ di Pisa Dipartimento di Matematica Pisa Italy

Using the concept of approximate algorithm it is shown that 6logn+66log⁡n+66\log n + 6 parallel steps and <span class=

Using the concept of approximate algorithm it is shown that

6 \log n + 6

$6\log n + 6$ parallel steps and

关键词： parallel matrix inversion Toeplitz matrices approximate algorithms band matrices

来源：评论

学校读者我要写书评

暂无评论

Uncertain lightweight ontologies in a product-based possibility theory framework

引用

INTERNATIONAL JOURNAL OF approximate REASONING 2017年 88卷 237-258页

作者： Boutouhami, Khaoula Benferhat, Salem Khellaf, Faiza Nouioua, Farid Univ Artois CRIL CNRS UMR 8188 F-62307 Lens France Univ Sci & Technol Houari Boumediene RIIMA Bab Ezzouar Algeria Aix Marseille Univ CNRS ENSAM Univ ToulonLSIS UMR 7296 Marseille France

This paper investigates an extension of lightweight ontologies, encoded here in DL-Lite languages, to the product-based possibility theory framework. We first introduce the language (and its associated semantics) used for representing uncertainty in lightweight ontologies. We show that, contrarily to a min-based possibilistic DL-Lite, query answering in a product-based possibility theory is a hard task. We provide equivalent transformations between the problem of computing an inconsistency degree (the key notion in reasoning from a possibilistic DL-Lite knowledge base) and the weighted maximum 2-Horn SAT problem. The last part of the paper provides an encoding of the problem of computing inconsistency degree in product-based possibility DL-Lite as a weighted set cover problem and the use of a greedy algorithm to compute an approximate value of the inconsistency degree. This encoding allows us to provide an approximate algorithm for answering instance checking queries in product-based possibilistic DL-Lite. Experimental studies show the quality of the approximate algorithms for both inconsistency degree computation and instance checking queries. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Lightweight ontologies Possibility theory Product-based possibility theory approximate algorithms Instance checking

来源：评论

学校读者我要写书评

暂无评论

Dynamic Hybrid algorithms for MAP Inference in Discrete MRFs

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2010年第10期32卷 1846-1857页

作者： Alahari, Karteek Kohli, Pushmeet Torr, Philip H. S. Oxford Brookes Univ Dept Comp Sch Technol Oxford OX33 1HX England Microsoft Res Cambridge Cambridge CB3 0FB England

In this paper, we present novel techniques that improve the computational and memory efficiency of algorithms for solving multilabel energy functions arising from discrete MRFs or CRFs. These methods are motivated by the observations that the performance of minimization algorithms depends on: 1) the initialization used for the primal and dual variables and 2) the number of primal variables involved in the energy function. Our first method (dynamic alpha-expansion) works by "recycling" results from previous problem instances. The second method simplifies the energy function by "reducing" the number of unknown variables present in the problem. Further, we show that it can also be used to generate a good initialization for the dynamic alpha-expansion algorithm by "reusing" dual variables. We test the performance of our methods on energy functions encountered in the problems of stereo matching and color and object-based segmentation. Experimental results show that our methods achieve a substantial improvement in the performance of alpha-expansion, as well as other popular algorithms such as sequential tree-reweighted message passing and max-product belief propagation. We also demonstrate the applicability of our schemes for certain higher order energy functions, such as the one described in [1], for interactive texture-based image and video segmentation. In most cases, we achieve a 10-15 times speed-up in the computation time. Our modified alpha-expansion algorithm provides similar performance to Fast-PD [2], but is conceptually much simpler. Both alpha-expansion and Fast-PD can be made orders of magnitude faster when used in conjunction with the "reduce" scheme proposed in this paper.

关键词： Markov random fields multilabel problems energy minimization approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Combining Solutions of the Axial Assignment Problem

引用

AUTOMATION AND REMOTE CONTROL 2021年第8期82卷 1418-1425页

作者： Afraimovich, L. G. Emelin, M. D. Lobachevsky State Univ Nizhny Novgorod Nizhnii Novgorod 603950 Russia

We consider the NP-hard integer three-index axial assignment problem. The task of optimal combination of the pairs of feasible solutions of the problem is posed, and a linear complexity algorithm for its solution is constructed. This algorithm can be used as a supplement to heuristic or approximate algorithms for the three-index assignment problem for post-processing the obtained approximate solutions of the problem. The results of computational experiments, which demonstrate the promising nature of our approach, are presented.

关键词： axial assignment problem multiindex problems approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Approaches to k Representative G-Skyline Queries

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2020年第5期14卷 58-58页

作者： Zhou, Xu Li, Kenli Yang, Zhibang Gao, Yunjun Li, Keqin Hunan Univ Coll Informat Sci & Engn Lushan Rd S Changsha Hunan Peoples R China Changsha Univ Coll Comp Engn & Appl Math 98 Hongshan Rd Changsha Peoples R China Zhejiang Univ Coll Comp Sci Hangzhou Peoples R China State Univ New York Sci Dept Comp Sci Sci Hall 2491 Hawk Dr New Paltz NY USA

The G-Skyline (GSky) query is a powerful tool to analyze optimal groups in decision support. Compared with other group skyline queries, it releases users from providing an aggregate function. Besides, it can get much comprehensive results without overlooking some important results containing non-skylines. However, it is hard for the users to make sensible choices when facing so many results the GSky query returns, especially over a large, high-dimensional dataset or with a large group size. In this article, we investigate k representative G-Skyline (kGSky) queries to obtain a manageable size of optimal groups. The kGSky query can also inherit the advantage of the GSky query;its results are representative and diversified. Next, we propose three exact algorithms with novel techniques including an upper bound pruning, a grouping strategy, a layered optimum strategy, and a hybrid strategy to efficiently process the kGSky query. Consider these exact algorithms have high time complexity and the precise results are not necessary in many applications. We further develop two approximate algorithms to trade off some accuracy for efficiency. Extensive experiments on both real and synthetic datasets demonstrate the efficiency, scalability, and accuracy of the proposed algorithms.

关键词： approximate algorithms data management group skyline query Progressive algorithms

来源：评论

学校读者我要写书评

暂无评论

Job grouping in surface mounted component printing

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 1999年第1期15卷 39-49页

作者： Smed, J Johnsson, M Puranen, M Leipälä, T Nevalainen, O Univ Turku Dept Mat Sci FIN-20014 Turku Finland Univ Turku Ctr Comp Sci FIN-20014 Turku Finland

The arrangement of operations in a production line for mounting the surface components on a printed circuit board is discussed. The production program includes a wide range of different products, which causes frequent set-up operations. The overall efficiency of the production line depends heavily on how the printing operations are organized. Set-ups cause delays which can be cut down by selecting carefully the feeders for the components and by solving a suitable sequence for the products. We describe an integrated production management system for job grouping. The system utilizes approximate algorithms for minimizing the number of component switching instants. A discussion of the exact minimization by using mathematical 0/1 integer programming approach is also given. The revision of the production management system has had a major impact on the productivity, and an increase of ca. 58 % in the number of component insertions per hour is observed. (C) 1999 Elsevier Science Ltd. All rights reserved.

关键词： printed circuit boards group technology approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

HeavySeparation: A Generic framework for stream processing faster and more accurate

引用

COMPUTER COMMUNICATIONS 2024年 223卷 36-43页

作者： Lu, Jie Chen, Hongchang Zhang, Zhen PLA Informat Engn Univ Zhengzhou Peoples R China Natl Digital Switching Syst Engn & Technol Res Ctr Zhengzhou Peoples R China Network Commun & Secur Purple Mt Lab Nanjing Peoples R China

Sketch as a probability data structure has been widely used in high volume, fast data streams. At the cost of a tiny accuracy in frequency estimation, it achieves a high speed with small memory usage. However, skewed data streams pose a significant challenge for existing sketches in terms of accuracy and speed using limited memory. To address this issue, we proposed a framework, called HeavySeparation, to enhance existing sketches by filtering elephant flow efficiently and accurately. We adopt a power -weakening increment strategy to allow sufficient competition in the early stages of identifying elephant flows and amplifying relative advantage when the frequency of candidate flow is large. To verify the effectiveness and efficiency of our framework, we apply the framework to two typical sketches and two common stream processing tasks. Results show that HeavySeparation framework reduces the error by around 1 -2 orders of magnitude on average compared to the state-of-the-art in frequency estimation.

关键词： Traffic measurement approximate algorithms Sketch

来源：评论

学校读者我要写书评

暂无评论

Further analysis of the remedian algorithm

引用

THEORETICAL COMPUTER SCIENCE 2013年 495卷 1-16页

作者： Cantone, Domenico Hofri, Micha Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Worcester Polytech Inst Dept Comp Sci Worcester MA 01609 USA

We present an analysis of the remedian, an efficient, known algorithm, for the approximate median selection problem, that is easy to implement. The algorithm can be used for data in an array, as well as for streaming data. In an array it performs in-place, recursively dividing the candidate values into sets of size b, from which exact medians are selected for the next phase. On streaming data it performs a filter operation, requiring, by the time n items are processed, the storage of log(b) n candidate entries. The contribution of the article is a precise characterization, combinatorial and asymptotic, of the accuracy of the algorithm, showing explicitly the role of the critical design parameter b. In addition, we compute the time and space costs of the algorithm, and present experimental illustrations of its accuracy. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Median selection problem Remedian algorithm approximate algorithms Probabilistic analysis Asymptotic bounds

来源：评论

学校读者我要写书评

暂无评论

Shapley Value Approximation Based on Complementary Contribution

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第12期36卷 9263-9281页

作者： Sun, Qiheng Zhang, Jiayao Liu, Jinfei Xiong, Li Pei, Jian Ren, Kui Zhejiang Univ Hangzhou 310027 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310027 Zhejiang Peoples R China Emory Univ Comp Sci & Biomed Informat Atlanta GA 30322 USA Duke Univ Trinity Coll Arts & Sci Dept Comp Sci Durham NC 27708 USA

Shapley value provides a unique way to fairly assess each player's contribution in a coalition and has enjoyed many applications. However, the exact computation of Shapley value is #P-hard due to the combinatoric nature of Shapley value. Many existing applications of Shapley value are based on Monte-Carlo approximation, which requires a large number of samples and the assessment of utility on many coalitions to reach high-quality approximation, and thus is still far from being efficient. Can we achieve an efficient approximation of Shapley value by smartly obtaining samples? In this paper, we treat the sampling approach to Shapley value approximation as a stratified sampling problem. Our main technical contributions are a novel stratification design and a sampling method based on Neyman allocation. Moreover, computing the Shapley value in a dynamic setting, where new players may join the game and others may leave it poses an additional challenge due to the considerable cost of recomputing from scratch. To tackle this issue, we propose to capture changes in Shapley value, making our approaches applicable to scenarios with dynamic players. Experimental results on several real data sets and synthetic data sets demonstrate the effectiveness and efficiency of our approaches.

关键词： Resource management Heuristic algorithms Games Data models Approximation algorithms Estimation Pricing approximate algorithms dynamic datasets shapley value

来源：评论

学校读者我要写书评

暂无评论

Approximation schemes for knapsack problems with shelf divisions

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期352卷 71-84页

作者： Xavier, EC Miyazawa, FK Univ Estadual Campinas Inst Comp BR-13084971 Campinas SP Brazil

Given a knapsack of size K, non-negative values d and Delta, and a set S of iterns, each item e epsilon S with size s(e) and value v(e), we define a shelf as a subset of items packed inside a bin with total items size at most Delta. Two subsequent shelves must be separated by a shelf divisor of size d. The size of a shelf is the total size of its iterns plus the size of the shelf divisor. The SHELF-KNAPSACK Problem (SK) is to find a subset S' subset of S partitioned into shelves with total shelves size at most K and maximum value. The CLASS CONSTRAINED SHELF KNAPSACK (CCSK) is a generalization of the problem SK, where each item in S has a class and each shelf in the solution must have only items of the same class. We present approximation schemes for the SK and the CCSK problems. To our knowledge, these are the first approximation results where shelves of non-null size are used in knapsack problems. (c) 2005 Elsevier B.V. All rights reserved.

关键词： approximate algorithms approximation schemes knapsack problem shelf packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：