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

arXiv 2025年

作者： Apte, Anuj Lee, Eunou Marwaha, Kunal Parekh, Ojas Sud, James University of Chicago United States Korea Institute for Advanced Study Korea Republic of Sandia National Laboratories

We introduce a 0.611-approximation algorithm for Quantum MaxCut and a 1+4√5 ≈ 0.809-approximation algorithm for the EPR Hamiltonian of [Kin23]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter. © 2025, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Iterative Recovery algorithms for Complex-Valued Distributed Compressed Sensing

Iterative Recovery Algorithms for Complex-Valued Distributed...

引用

International ITG Conference on Source and Channel Coding (SCC)

作者： Elena Sterk Robert F.H. Fischer Institute of Communications Engineering Ulm University Germany

ISBN: (数字)9798331522896

ISBN: (纸本)9798331522902

Distributed compressed sensing aims at the joint reconstruction of sparse signals with a common support. In some applications, complex-valued signals and sensing matrices are present. In this paper, we investigate recovery algorithms for complex-valued distributed scenarios. To that end, we review a compact exposition of complex- and vector-valued MMSE estimators. These can be used in approximate-message-passing-type algorithms. We explain joint reconstruction via iterative algorithms and evaluate suitable recovery algorithms. The performance of these algorithms is evaluated by numerical simulations for different scenarios.

关键词： Reviews approximation algorithms Numerical simulation Iterative algorithms Encoding Sensors Sparse matrices Compressed sensing

来源：评论

学校读者我要写书评

暂无评论

Fair Division Beyond Monotone Valuations

arXiv

引用

arXiv 2025年

作者： Barman, Siddharth Verma, Paritosh Indian Institute of Science India Purdue University United States

This paper studies fair division of divisible and indivisible items among agents whose cardinal preferences are not necessarily monotone. We establish the existence of fair divisions and develop approximation algorithms to compute them. We address two complementary valuation classes, subadditive and nonnegative, which go beyond monotone functions. Considering both the division of cake (divisible resources) and allocation of indivisible items, we obtain fairness guarantees in terms of (approximate) envy-freeness (EF) and equability (EQ). In the context of envy-freeness, we prove that an EF division of a cake always exists under cake valuations that are subadditive and globally nonnegative (i.e., the value of the entire cake for every agent is nonnegative, but parts of the cake can be burnt). This result notably complements the nonexistence of EF allocations for burnt cakes known for more general valuations. For envy-freeness in the indivisible-items setting, we establish the existence of EF3 allocations for subadditive and globally nonnegative valuations;again, such valuations can be non-monotone and can impart negative value to specific item subsets. In addition, we obtain universal existence of EF3 allocations under nonnegative valuations. We study equitability under nonnegative valuations. Here, we prove that EQ3 allocations always exist when the agents’ valuations are nonnegative (and possibly non-monotone). Also, in the indivisible-items setting, we develop an approximation algorithm that, for given nonnegative valuations, finds allocations that are equitable within additive margins. Our results have combinatorial implications. For instance, the developed results imply: (i) The universal existence of proximately dense subgraphs: Given any graph G = (V, E) and integer k (at most |V |), there always exists a partition V1, V2, . . ., Vk of the vertex set such that the edge densities within the parts, Vi, are additively within four of each other, and (ii) The univer

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Algorithm for Load Distribution Between Computing Resources of Cloud Environments

Dynamic Algorithm for Load Distribution Between Computing Re...

引用

International Russian Smart Industry Conference (SmartIndustryCon)

作者： Valery P. Mochalov Natal'ya Yu. Bratchenko Dar'ya V. Gosteva Department of Digital Robotic Systems and Electronics Institute of Advanced Engineering North-Caucasus Federal University Stavropol Russia

ISBN: (数字)9798331511241

ISBN: (纸本)9798331511258

The article considers the development of a dynamic algorithm for distributing and balancing the load, characterized by nonlinear parameters and fractal structure, between the computing resources of cloud data centers (DCs). A rationale is given for the application of methods of nonlinear dynamics and chaos theory to solving this problem, which is based on the topological similarity of the behavior of deterministic chaotic systems and the input network load of the data center. The load randomness test was conducted by calculating Lyapunov indices. To eliminate noise components of network traffic, the principal component method of its time series was applied. The problem of phase space reconstruction is solved by the delay method based on the embedding theorem and the average mutual information method. Based on this reconstruction, a method for predicting the load dynamics was developed. It was presented in the form of a system of discrete mappings connected by an algebraic polynomial, providing successful prediction of irregular time series and forming the basis for constructing a matrix for distributing data center resources. The aim of the article is to increase the efficiency of using the resources of data center cluster servers in conditions of a fractal structure of the network load by developing a dynamic algorithm for its distribution and balancing based on nonlinear dynamics methods.

关键词： Data centers Heuristic algorithms Time series analysis Clustering algorithms Telecommunication traffic approximation algorithms Dynamic scheduling Polynomials Nonlinear dynamical systems Servers

来源：评论

学校读者我要写书评

暂无评论

Min-max coverage problems on tree-like metrics

引用

Procedia Computer Science 2023年 223卷 148-156页

作者： Eric Aaron Úrsula Hébert-Johnson Danny Krizanc Daniel Lokshtanov Colby College Waterville ME 04901 USA University of California Santa Barbara 93106 USA Wesleyan University Middletown CT 06457 USA

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the Min-Max Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of Min-Max Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-Traveling Salesmen Problem. In the Min-Max Tree Cover problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, Min-Max k-Rooted Tree Cover, the input also contains k roots r 1 , . . ., r k , and the i th tree must contain the root r i . These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an n O(k) -time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-Traveling Salesmen Problem, Min-Max Path Cover, and Min-Max Tree Cover on graphs of bounded treewidth.

关键词： approximation algorithms Parameterized algorithms Min-max coverage Treewidth Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Energy Efficiency Optimization for RIS-Aided Systems Using a Measured Power Model

Energy Efficiency Optimization for RIS-Aided Systems Using a...

引用

IEEE Conference on Wireless Communications and Networking

作者： Shuwen Lin Jian Sang Xiao Li Wankai Tang Marco Di Renzo Shi Jin National Mobile Communications Research Laboratory Southeast University Nanjing China CNRS CentraleSupélec Laboratoire des Signaux et Systèmes Université Paris-Saclay Gif-sur-Yvette France Department of Engineering King's College London Centre for Telecommunications Research London United Kingdom

ISBN: (数字)9798350368369

ISBN: (纸本)9798350368376

Reconfigurable intelligent surface (RIS) technology has gained wide recognition for its ability of enhancing the performance of wireless communication systems. This paper investigates the energy efficiency (EE) of a discrete phase shift RIS-assisted multi-cell communication system. Assuming that only statistical channel state information is available, we maximize the EE under a practical measured-based RIS power consumption model. Approximating the discrete measured-based RIS power consumption model by a continuous differentiable function, the problem is addressed by jointly optimizing the transmit beamforming at the base stations and the RIS phase shift matrix, by using fractional programming and complex circle manifold techniques. Simulation results demonstrate that the proposed algorithm can effectively achieve near-optimal EE performance and low RIS power consumption.

关键词： Wireless communication Power demand Power measurement Array signal processing Simulation Reconfigurable intelligent surfaces approximation algorithms Energy efficiency Optimization Channel state information

来源：评论

学校读者我要写书评

暂无评论

An Improved FastICA Algorithm Using Correction Factors And Lanczos Algorithm For EEG Signals

An Improved FastICA Algorithm Using Correction Factors And L...

引用

algorithms, Computing and Machine Learning (CACML), Asia Conference on

作者： Qinghui Zhu Junqi Huang Hongyi Zhang Huaili Jiang Xingen Gao Zhengzhe Zhong SOCE XMUT Xiamen China Fujian Key Laboratory of Industrial Internet & loT Xiamen Intretech Inc. Xiamen Peiyang BCI & Smart Health Innovation Research Institution Xiamen China

ISBN: (数字)9798331543143

ISBN: (纸本)9798331543150

Independent Component Analysis (ICA) is a powerful technique for source separation, particularly in scenarios where prior knowledge is unavailable. However, the conventional FastICA algorithm often suffers from slow convergence and a high iteration count, limiting its applicability in real-time scenarios. This paper proposes an improved FastICA algorithm that addresses these limitations by reducing computational time and iteration count. Specifically, incorporating an inexact correction factor reduces the average number of iterations by 5.13%. By setting the correction term to 0.993 and introducing a random initial matrix with parameter values of 96, the algorithm achieves a 29.20% improvement in computational efficiency. Furthermore, applying the Lanczos algorithm for whitening further improves performance. When the parameter values of the random initial matrix is adjusted to 72, the number of iterations is reduced by 28.65%. Combining a correction term of 0.999 with parameter values of the random initial matrix are 72 yields an overall efficiency improvement of approximately 35.11%, demonstrating a significant advancement over the original FastICA algorithm.

关键词： Machine learning algorithms Signal processing algorithms approximation algorithms Data processing Electroencephalography Blind source separation Real-time systems Computational efficiency Signal analysis Convergence

来源：评论

学校读者我要写书评

暂无评论

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

arXiv

引用

arXiv 2025年

作者： Fei, Yumou Minzer, Dor Wang, Shuo Department of EECS Massachusetts Institute of Technology United States Department of Mathematics Massachusetts Institute of Technology United States

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph G = (V, E) in some fixed order, and its goal is to approximate the size of the largest cut in G. Improving upon an earlier result of Kapralov, Khanna and Sudan, it was shown by Kapralov and Krachun that for all Ε > 0, no o(n) memory streaming algorithm can achieve a (1/2 + Ε)-approximation for Max-Cut. Their result holds for single-pass streams, i.e. the setting in which the algorithm only views the stream once, and it was open whether multi-pass access may help. The state-of-the-art result along these lines, due to Assadi and N, rules out arbitrarily good approximation algorithms with constantly many passes and n1−δ space for any δ > 0. We improve upon this state-of-the-art result, showing that any non-trivial approximation algorithm for Max-Cut requires either polynomially many passes or polynomially large space. More specifically, we show that for all Ε > 0, a k-pass streaming (1/2 + Ε)-approximation algorithm for Max-Cut requires ΩΕ (n1/3/k) space. This result leads to a similar lower bound for the Maximum Directed Cut problem, showing the near optimality of the algorithm of [Saxena, Singer, Sudan, Velusamy, SODA 2025]. Our lower bounds proceed by showing a communication complexity lower bound for the Distributional Implicit Hidden Partition (DIHP) Problem, introduced by Kapralov and Krachun. While a naive application of the discrepancy method fails, we identify a property of protocols called "globalness", and show that (1) any protocol for DIHP can be turned into a global protocol, (2) the discrepancy of a global protocol must be small. The second step is the more technically involved step in the argument, and therein we use global hypercontractive inequalities, and more specifically strong quantitative versions of the level d inequality for global functions. © 2025, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fusion of Information in Multiple Particle Filtering in the Presence of Unknown Static Parameters

Fusion of Information in Multiple Particle Filtering in the ...

引用

International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Xiaokun Zhao Marija Iloska Yousef El-Laham Monica F. Bugallo Department of Electrical and Computer Engineering Stony Brook University Stony Brook NY USA

ISBN: (数字)9798350368741

ISBN: (纸本)9798350368758

An important and often overlooked aspect of particle filtering methods is the estimation of unknown static parameters. A simple approach for addressing this problem is to augment the unknown static parameters as auxiliary states that are jointly estimated with the time-varying parameters of interest. This can be impractical, especially when the system of interest is high-dimensional. Multiple particle filtering (MPF) methods were introduced to try to overcome the curse of dimensionality by using a "divide and conquer" approach, where the vector of unknowns is partitioned into a set of subvectors, each estimated by a separate particle filter. Each particle filter weighs its own particles by using predictions and estimates communicated from the other filters. Currently, there is no principled way to implement MPF methods where the particle filters share unknown parameters or states. In this work, we propose a fusion strategy to allow for the sharing of unknown static parameters in the MPF setting. Specifically, we study the systems which are separable in states and observations. It is proved that optimal Bayesian fusion can be obtained for state-space models with non-interacting states and observations. Simulations are performed to show that MPF with fusion strategy can provide more accurate estimates within fewer time steps comparing to existing algorithms.

关键词： Signal processing algorithms Estimation approximation algorithms Particle filters Vectors Acoustics State-space methods Partitioning algorithms Bayes methods Speech processing

来源：评论

学校读者我要写书评

暂无评论

Hybrid Receiver Design for Massive MIMO-OFDM with Low-Resolution ADCs and Oversampling

Hybrid Receiver Design for Massive MIMO-OFDM with Low-Resolu...

引用

IEEE Conference on Wireless Communications and Networking

作者： Mengyuan Ma Nhan Thanh Nguyen Italo Atzeni Markku Juntti Centre for Wireless Communications (CWC) University of Oulu Finland

ISBN: (数字)9798350368369

ISBN: (纸本)9798350368376

Low-resolution analog-to-digital converters (ADCs) and hybrid beamforming have emerged as efficient solutions to reduce power consumption with satisfactory spectral efficiency (SE) in massive multiple-input multiple-output (MIMO) systems. In this paper, we investigate the performance of a hybrid receiver in massive MIMO orthogonal frequency-division multiplexing (OFDM) uplink systems with low-resolution ADCs and over-sampling. Considering both the temporal and spatial correlation of the quantization distortion (QD), we derive a closed-form approximation of the frequency-domain QD covariance matrix, which facilitates the evaluation of the system's SE. Then we jointly design the analog and digital combiners of the hybrid receiver to maximize the SE. The formulated problem is challenging due to the constant-modulus constraint of the analog combiner and its coupling with the digital one. To overcome these challenges, we transform the objective function into an equivalent but more tractable form and then iteratively update the analog and digital combiners. Numerical simulations verify the superiority of the proposed algorithm over the considered benchmarks and show the resilience of the hybrid receiver to beam squint with low-resolution ADCs. Furthermore, the proposed hybrid receiver design with oversampling can achieve significantly higher energy efficiency compared with the fully digital one.

关键词： Spectral efficiency Frequency-domain analysis Receivers Transforms Benchmark testing Numerical simulation approximation algorithms Energy efficiency Covariance matrices Uplink

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：