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

IEEE TRANSACTIONS ON QUANTUM ENGINEERING 2025年第1期6卷 1-15页

作者： Li, Sanjiang Zhou, Xiangzhen Feng, Yuan Univ Technol Sydney Fac Engn & Informat Technol Ctr Quantum Software & Informat Ultimo NSW 2007 Australia Nanjing Tech Univ Nanjing 210037 Peoples R China Tsinghua Univ Dept Comp Sci & Technol Beijing 100190 Peoples R China

Current superconducting quantum devices impose strict connectivity constraints on quantum circuit execution, necessitating circuit transformation before executing quantum circuits on physical hardware. Numerous quantum circuit transformation (QCT) algorithms have been proposed. To enable faithful evaluation of state-of-the-art QCT algorithms, this article introduces qubit mapping benchmark with known near-optimality (QKNOB), a novel benchmark construction method for QCT. QKNOB circuits have built-in transformations with near-optimal (close to the theoretical optimum) swap count and depth overhead. QKNOB provides general and unbiased evaluation of QCT algorithms. Using QKNOB, we demonstrate that SABRE, the default Qiskit compiler, consistently achieves the best performance on the 53-qubit IBM Q Rochester and Google Sycamore devices for both swap count and depth objectives. Our results also reveal significant performance gaps relative to the near-optimal transformation costs of QKNOB. Our construction algorithm and benchmarks are open-source.

关键词： Logic gates Qubit Quantum circuit Benchmark testing Performance evaluation Costs approximation algorithms Quantum mechanics Transforms Scalability Architecture hardware/software co-design performance optimization placement routing

来源：评论

学校读者我要写书评

暂无评论

Deterministic-Iterative Integrated Phase Retrieval

引用

IEEE PHOTONICS TECHNOLOGY LETTERS 2024年第22期36卷 1341-1344页

作者： Jiang, Jixin Li, Fanxing Yu, Siyang Yang, Fan Liu, Jixiao Wang, Jian Yan, Wei Du, Jialin Chinese Acad Sci Natl Key Lab Opt Field Manipulat Sci & Technol Chengdu 610209 Peoples R China Chinese Acad Sci Inst Opt & Elect Chengdu 610209 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

In multi-plane phase retrieval imaging, the accuracy and efficiency of phase retrieval algorithm are usually mutually restrictive. Specifically, deterministic algorithms struggle to achieve sufficient accuracy, while iterative algorithms consume excessive time, thereby limiting their practical application. To address this issue, we propose a deterministic-iterative integrated phase retrieval algorithm, that is, an approximate phase, which could be quickly obtained by the deterministic algorithm, is imported as an initial value into the iterative algorithm to retrieve more accurate result efficiently. To demonstrate the effectiveness of this algorithm, we simulate its performance under various iterations and diffraction distances. Additionally, experiments are conducted using a pure-phase USAF1951 target and fixed mouse fibroblasts to verify its feasibility, high accuracy, and rapid iterative convergence speed. Integrating the deterministic and iterative algorithms, this method offers a novel approach for enhancing phase retrieval.

关键词： Accuracy Optical diffraction Diffraction Optical imaging Charge coupled devices Adaptive optics approximation algorithms Convergence Optical scattering Iterative algorithms Deterministic-iterative integrated algorithm quantitative phase imaging phase retrieval biological imaging

来源：评论

学校读者我要写书评

暂无评论

A (1.5+ε)-approximation Algorithm for Weighted Connectivity Augmentation 2023

A (1.5+ε)-Approximation Algorithm for Weighted Connectivity...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Traub, Vera Zenklusen, Rico Univ Bonn Bonn Germany Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450399135

Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural 2-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below 2 can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a (1.5 +epsilon)-approximation algorithm forWCAP, showing for the first time that factors below 2 are achievable. On a high level, we design a well-chosen local search algorithm, inspired by recent advances for Weighted Tree Augmentation. To measure progress, we consider a directed weakening of WCAP and show that it has highly structured planar solutions. Interpreting a solution of the original problem as one of this directed weakening allows us to describe local exchange steps in a clean and algorithmically amenable way. Leveraging these insights, we show that we can efficiently search for good exchange steps within a component class of link sets that is closely related to bounded treewidth subgraphs of circle graphs. Moreover, we prove that an optimum solution can be decomposed into smaller components, at least one of which leads to a good local search step as long as we did not yet achieve the claimed approximation guarantee.

关键词： weighted connectivity augmentation approximation algorithms combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Positional Knapsack Problem: NP-hardness and approximation scheme 12

Positional Knapsack Problem: NP-hardness and approximation s...

引用

12th Latin-American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Pedrosa, Lehilton L. C. da Silva, Mauro R. C. Schouery, Rafael C. S. Univ Estadual Campinas Inst Comp Ave Albert Einstein1251 Cidade Univ BR-13083852 Campinas SP Brazil

We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： approximation algorithms NP-Hardness FPTAS

来源：评论

学校读者我要写书评

暂无评论

A Time-Aggregated Model-Free RL Algorithm for Optimal Containment Control of MASs

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2024年第7期71卷 3393-3397页

作者： Shi, Xiongtao Li, Yanjie Du, Chenglong Gui, Weihua Harbin Inst Technol Shenzhen Sch Mech Engn & Automat Shenzhen 518055 Peoples R China Cent South Univ Sch Automat Changsha 410083 Peoples R China

In this brief, the optimal containment control problem for a class of unknown nonlinear multi-agent systems (MASs) is studied via a time-aggregated (TA) model-free reinforcement learning (RL) algorithm. First, based on the idea of TA, the control policy is updated only when the system visits a finite subset of the state space. Thus, the control is event-triggered and not time-triggered. On this basis, a model-free TA-based value iteration (TA-VI) algorithm is proposed to learn the optimal control protocol. Since the finite important states are considered and the control is event-triggered, this algorithm requires fewer updating times and fewer computation than the conventional optimal containment control. Moreover, the TA-VI algorithm eliminates requirements on the function approximator and state discretization, which allows a strict convergence analysis via the mathematical induction method. Finally, simulation results are given to show the feasibility and superiority of the proposed algorithm.

关键词： approximation algorithms Aerospace electronics Protocols Forestry Convergence Process control Performance analysis Time-aggregated reinforcement learning value iteration model-free learning optimal containment control

来源：评论

学校读者我要写书评

暂无评论

Breaching the 2 LMP approximation Barrier for Facility Location with Applications to k-Median 34

Breaching the 2 LMP Approximation Barrier for Facility Locat...

引用

34th ACM-SIAM Annual Symposium on Discrete algorithms (SODA)

作者： Viallat, Vincent Cohen-Addad Grandoni, Fabrizio Lee, Euiwoong Schwiegelshohn, Chris Google Res Mountain View CA 94043 USA IDSIA Lugano Switzerland Univ Michigan Ann Arbor MI 48109 USA Aarhus Univ Aarhus Denmark

ISBN: (纸本)9781611977554

The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients C and a set of facilities F in a metric space (C. F, dist) with facility costs open : F -> R+, the goal is to find a set of facilities S subset of F to minimize the sum of the opening cost open(S) and the connection cost d(S) := Sigma(p is an element of C) min(c is an element of S) dist(p, c). An algorithm for UFL is called a Lagrangian Multiplier Preserving (LMP) alpha approximation if it outputs a solution S subset of F satisfying open(S) + d(S) <= open(S *) + alpha d(S*) for any S* subset of F. The best-known LMP approximation ratio for UFL is at most 2 by the JMS algorithm of Jain, Mahdian, and Saberi [STOC'02, ***'03] based on the Dual-Fitting technique. The lack of progress on improving the upper bound on aLMP in the last two decades raised the natural question whether alpha(LMP) = 2. We answer this question negatively by presenting a (slightly) improved LMP approximation algorithm for UFL. This is achieved by combining the Dual-Fitting technique with Local Search, another popular technique to address clustering problems. In more detail, we use the LMP solution S produced by JMS to seed a local search algorithm. We show that local search substantially improves S unless a big fraction of the connection cost of S is associated with facilities of relatively small opening costs. In the latter case however the analysis of Jain, Mahdian, and Saberi can be improved (i.e., S is cheaper than expected). To summarize: Either S is close enough to the optimum, or it must belong to the local neighborhood of a good enough local optimum. From a conceptual viewpoint, our result gives a theoretical evidence that local search can be enhanced so as to avoid bad local optima by choosing the initial feasible solution with LP-based techniques. Our result directly implies a (slightly) improved approximation for the related k-Median problem, another fundamenta

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Set Encoding with Universal Mini-Batch Consistency and Unbiased Full Set Gradient approximation 40

Scalable Set Encoding with Universal Mini-Batch Consistency ...

引用

40th International Conference on Machine Learning

作者： Willette, Jeffrey Lee, Seanie Andreis, Bruno Kawaguchi, Kenji Lee, Juho Hwang, Sung Ju Korea Adv Inst Sci & Technol Daejeon South Korea Natl Univ Singapore Singapore Singapore

Recent work on mini-batch consistency (MBC) for set functions has brought attention to the need for sequentially processing and aggregating chunks of a partitioned set while guaranteeing the same output for all partitions. However, existing constraints on MBC architectures lead to models with limited expressive power. Additionally, prior work has not addressed how to deal with large sets during training when the full set gradient is required. To address these issues, we propose a Universally MBC (UMBC) class of set functions which can be used in conjunction with arbitrary non-MBC components while still satisfying MBC, enabling a wider range of function classes to be used in MBC settings. Furthermore, we propose an efficient MBC training algorithm which gives an unbiased approximation of the full set gradient and has a constant memory overhead for any set size for both train- and test-time. We conduct extensive experiments including image completion, text classification, unsupervised clustering, and cancer detection on high-resolution images to verify the efficiency and efficacy of our scalable set encoding framework. Our code is available at ***/jeffwillette/umbc

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Robust WMMSE-Based Precoder With Practice-Oriented Design for Massive MU-MIMO

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2024年第7期13卷 1858-1862页

作者： Wang, Kexuan Liu, An Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Peoples R China

The challenge induced by imperfect channel state information (CSI) at the transmitter promotes the research of robust precoder design, among which stochastic weighted minimum mean square error (SWMMSE) has gained wide attention due to its excellent performance. However, its considerable computational complexity and extremely slow convergence rate make it impractical to be applied in real massive multi-user multiple-input (MU-MIMO) systems. To combat these drawbacks, in this letter, we first propose a robust weighted minimum mean square error (WMMSE)-based precoder with a practice-oriented design, namely PO-WMMSE. On one hand, it can be approximately seen as a deterministic equivalent of the classical SWMMSE, and thus yield a satisfying performance. On the other hand, due to the low complexity and closed-form approximation of the expectation terms in PO-WMMSE, it can quickly converge with linear complexity (in contrast, the expectation terms are approximated using sample average in SWMMSE). Then, the proposed algorithm is unfolded into a layer-wise neural network, namely PO-WMMSE Net, in which several trainable matrices are induced to compensate for the approximate loss and further accelerate convergence. Finally, numerical comparisons under imperfect CSI with existing algorithms demonstrate the significant advantages of the developed PO-WMMSE Net.

关键词： Convergence approximation algorithms Neural networks Complexity theory Precoding Mean square error methods Iterative algorithms Robust WMMSE linear precoder deep unfolding

来源：评论

学校读者我要写书评

暂无评论

Clustering What Matters: Optimal approximation for Clustering with Outliers 37

Clustering What Matters: Optimal Approximation for Clusterin...

引用

37th AAAI Conference on Artificial Intelligence (AAAI) / 35th Conference on Innovative Applications of Artificial Intelligence / 13th Symposium on Educational Advances in Artificial Intelligence

作者： Agrawal, Akanksha Inamdar, Tanmay Saurabh, Saket Xue, Jie Indian Inst Technol Madras Chennai Tamil Nadu India Univ Bergen Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India New York Univ Shanghai Shanghai Peoples R China

ISBN: (纸本)9781577358800

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two integers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f (k, m) . n(O(1)) for some function f), that almost matches the approximation ratio for its outlier-free counter-part. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-MEDIAN and k-MEANS with outliers in general metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation Algorithm for Min-max Correlation Clustering Problem with Penalties 17th

Approximation Algorithm for Min-max Correlation Clustering P...

引用

17th International Conference on Combinatorial Optimization and Applications, COCOA 2024

作者： Huang, Yuebo Ji, Sai Tian, Xiaoyun Zhou, Kun Institute of Mathematics Hebei University of Technology Tianjin300401 China Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing100190 China Digital Technology Management Hoseo University Chonan42409 Korea Republic of

ISBN: (纸本)9789819644445

This paper introduces the min-max correlation clustering problem with penalties, which is a generalization of the correlation clustering problem. In this problem, each vertex can be clustered or penalized, and the goal of the problem is to minimize the sum of the number of error edges and the penalty cost at the worst vertex. In this paper, we give an integer programming and linear programming relaxation of the problem, and provide a constant approximation algorithm of the problem based on LP-rounding technique. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：