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

Practical algorithm for minimum cost submodular cover problem with performance guarantees

OPTIMIZATION LETTERS 2025年 1-24页

作者： Pham, Canh V. Tran, Tan D. Ha, Dung T. K. Phu, Quat V. Phenikaa Univ Fac Comp Sci ORLab Hanoi Vietnam VNU Univ Engn & Technol Hanoi Vietnam

In this work, we consider the Minimum Cost Submodular Cover (MCSC) problem over a ground set of size n, which aims at finding a subset with the minimal cost required such that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of artificial intelligence and combinatorial optimization, such as spreading and detecting information in social networks, data summuraization, recommendation systems, etc. However, the best approximation algorithm for the problem requires an expensive query complexity of O(n(2)) that may become infeasible for some real applications with a massive size of data. To address this issue, we propose a bicriteria approximation algorithm that keeps the performance guarantees but significantly reduces the required number of queries and running time than the cutting- edge algorithm. In particular, our algorithm returns a ((1 + epsilon)(1 + log(1/delta)), 1 - delta)-bicriteria ratio and takes O(n log n) query complexity, where epsilon, delta > 0 are constant parameters. Besides the theoretical analysis, we conduct extensive experiments on two applications: Twitter feed summarization threshold and threshold influence in social networks. The results demonstrate that our algorithm outperforms the stateof-the-art regarding solution quality and query complexity.

关键词： Combinatorial optimization Submodular cover Bicriteria approximation query complexity

来源：评论

学校读者我要写书评

暂无评论

A formal algebra for document-oriented NoSQL data warehouses: formalisation and evaluation

引用

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS 2025年第3期28卷 1-30页

作者： Bouaziz, Senda Boukettaya, Soumaya Nabli, Ahlem Gargouri, Faiez MIRACL Lab Sfax Tunisia Sfax Univ Fac Econ & Management Sfax Sfax Tunisia Al Baha Univ Fac Comp Sci & Informat Technol Al Bahah Saudi Arabia Sfax Univ Inst Comp Sci & Multimedia Sfax Tunisia

"Not Only SQL" (NoSQL) solutions are becoming increasingly widespread in modern data warehouses. However, integrating these solutions, known for their schema-less structures, introduces a significant challenge when engaging in online analytical processing. A notable challenge is the lack of standardized representation for various online analytical processing operations (OLAP). Furthermore, managing and handling data with varying or absent schemes can introduce complexities and interfere with the smooth execution of OLAP operations. This paper aims to deal with the prior challenge. We propose an innovative algebra designed for OLAP operations in document-oriented NoSQL data warehouses. This OLAP algebra encloses essential operators like Project, Select, Union and Aggregate as well as more complex operators such as Slice, Dice, Roll-up, Drill-down, and Pivot. Introducing an algebra for OLAP operators in NoSQL databases improves performance, standardizes operations, simplify data analysis, and maximizes flexibility and scalability. To assess the effectiveness of the proposed algebra, we conducted a comprehensive evaluation using a COVID-19 case study implemented under MongoDB.

关键词： OLAP algebra Data warehouse NoSQL document-oreinted Algebraic operators query complexity query execution

来源：评论

学校读者我要写书评

暂无评论

Optimal randomized algorithms of weakly-balanced multi-branching AND-OR trees

引用

INFORMATION PROCESSING LETTERS 2025年 187卷

作者： Ito, Fuki Tokyo Metropolitan Univ 1-1 Minamiosawa Hachioji Tokyo 1920397 Japan

This article treats AND -OR tree computation in terms of query complexity. We are interested in the cases where assignments (inputs) or algorithms are randomized. For the former case, it is known that there is a unique randomized assignment achieving the distributional complexity of balanced trees. On the other hand, the dual problem has the opposite result;the optimal randomized algorithms for balanced trees are not unique. We extend the latter study on randomized algorithms to weakly -balanced trees, and see that the uniqueness still fails.

关键词： Computational complexity AND-OR tree Game tree Randomized algorithm query complexity

来源：评论

学校读者我要写书评

暂无评论

Experimental study of Forrelation in nuclear spins

引用

Science Bulletin 2017年第7期62卷 497-502页

作者： Hang Li Xun Gao Tao Xin Man-Hong Yung Guilu Long State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics Tsinghua University Beijing 100084 China Collaborative Innovation Centre of Quantum Matter Beijing 100084 China Centre for Quantum Information Institute for Interdisciplinary Information Sciences Tsinghua University Beijing 100084 China Institute for Quantum Science and Engineering and Department of Physics Southern University of Science and Technology Shenzhen 518055 China

Correlation functions are often employed to quantify the relationships among interdependent variables or sets of ***,a new class of correlation functions,called FORRELATION,has been introduced by Aaronson and Ambainis for studying the query complexity of quantum *** was found that there exists a quantum query algorithm solving 2-fold FORRELATION problems with an exponential quantum speedup over all possible classical means,which represents essentially the largest possible separation between quantum and classical query *** we report an experimental study probing the2-fold and 3-fold FORRELATIONS encoded in nuclear *** major experimental challenge is to control the spin fluctuation to within a threshold value,which is achieved by developing a set of optimized GRAPE pulse ***,our small-scale implementation indicates that the quantum query algorithm is capable of determining the values of FORRELATIONS within an acceptable accuracy required for demonstrating quantum supremacy,given the current technology and in the presence of experimental noise.

关键词： Forrelation query complexity Nuclear magnetic resonance Gradient ascent pulse engineering

来源：评论

学校读者我要写书评

暂无评论

Some results on approximate 1-median selection in metric spaces

引用

THEORETICAL COMPUTER SCIENCE 2012年 426卷 1-12页

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Tao Yuan Taiwan

A 1-median in a finite metric space is a point with the minimum average distance to all other points. Given a positive integer n and oracle access to a distance metric on {1, 2,..., n}, we study the problem of finding a 1-median. In particular, we show the nonexistence of (1) deterministic O(1)-approximation o(n)-query algorithms, (2) deterministic (2 - Omega(1))-approximation o(n(2))-query algorithms for graph metrics, (3) deterministic (3 - Omega(1))-approximation o(n(2))-query algorithms and (4) Monte-Carlo (2 - Omega(1))-approximation o(n)-query algorithms with an Omega(1) probability of success. We also show a Monte-Carlo (2 + epsilon)-approximation O((log(2)(1/epsilon))/epsilon(3))-query algorithm with a 1 - O(epsilon) probability of success, where epsilon is an element of (0. 1). (C) 2011 Elsevier B.V. All rights reserved.

关键词： Closeness centrality 1-median Metric space query complexity

来源：评论

学校读者我要写书评

暂无评论

Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights

引用

QUANTUM INFORMATION PROCESSING 2011年第2期10卷 177-188页

作者： Choi, Byung-Soo Braunstein, Samuel L. Ewha Womans Univ Dept Elect Engn Seoul South Korea Univ York Dept Comp Sci York YO10 5DD N Yorkshire England

As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0 < w(1) < w(2) < 1, w(1) + w(2) = 1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0 < w(1) < w(2) < 1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0 < w(1) < w(2) < center dot center dot center dot < w(m) < 1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, theweight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem.

关键词： Quantum algorithm Generalized weight decision problem query complexity

来源：评论

学校读者我要写书评

暂无评论

Quantum counterfeit coin problems

引用

THEORETICAL COMPUTER SCIENCE 2012年 456卷 51-64页

作者： Iwama, Kazuo Nishimura, Harumichi Raymond, Rudy Teruyama, Junichi Nagoya Univ Grad Sch Informat Sci Chikusa Ku Nagoya Aichi 4648601 Japan Kyoto Univ Sch Informat Kyoto 6068501 Japan IBM Res Tokyo Yamato 2428502 Japan

The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only "balanced" or "tilted" information and that we know the number k of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let Q(k, N) be the quantum query complexity of finding all k false coins from the N given coins. We show that for any k and N such that k < N/2, Q(k, N) = O(k(1/4)), contrasting with the classical query complexity, Omega (k log(N/k)), that depends on N. So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs Omega(k(1/4)) queries. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Counterfeit coin problems Quantum computing query complexity

来源：评论

学校读者我要写书评

暂无评论

FAIRLY ALLOCATING MANY GOODS WITH FEW QUERIES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 788-813页

作者： Oh, Hoon Procaccia, Ariel D. Suksompong, Warut Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Natl Univ Singapore Sch Comp Singapore 117417 Singapore

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic utilities, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive utilities and that a polylogarithmic bound holds for three agents with monotonic utilities. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envy-freeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive utilities.

关键词： envy-freeness fair division algorithms query complexity

来源：评论

学校读者我要写书评

暂无评论

Nondeterministic quantum query and communication complexities

引用

SIAM JOURNAL ON COMPUTING 2003年第3期32卷 681-699页

作者： De Wolf, R Ctr Wiskunde & Informat NL-1098 SJ Amsterdam Netherlands

We study nondeterministic quantum algorithms for Boolean functions f. Such algorithms have positive acceptance probability on input x iff f(x) = 1. In the setting of query complexity, we show that the nondeterministic quantum complexity of a Boolean function is equal to its "nondeterministic polynomial" degree. We also prove a quantum-vs.-classical gap of 1 vs. n for nondeterministic query complexity for a total function. In the setting of communication complexity, we show that the nondeterministic quantum complexity of a two-party function is equal to the logarithm of the rank of a nondeterministic version of the communication matrix. This implies that the quantum communication complexities of the equality and disjointness functions are n + 1 if we do not allow any error probability. We also exhibit a total function in which the nondeterministic quantum communication complexity is exponentially smaller than its classical counterpart.

关键词： quantum computing query complexity communication complexity nondeterminism

来源：评论

学校读者我要写书评

暂无评论

Algorithms for Boolean function query properties

引用

SIAM JOURNAL ON COMPUTING 2003年第5期32卷 1140-1157页

作者： Aaronson, S Bell Labs Murray Hill NJ 07974 USA

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities;block sensitivity;certificate complexity;and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N = 2(n)) as input. Our main results are the following: - O(N log(2) (3) log N) algorithms for many common properties, - an O(Nlog(2) (5) log N) algorithm for block sensitivity, - an O( N) algorithm for testing "quasi symmetry," - a notion of a " tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log(2) (3) log N) algorithm for finding it, - a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.

关键词： algorithm Boolean function truth table query complexity quantum computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：