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

ECONOMICAL CONVEX COVERINGS AND APPLICATIONS

SIAM JOURNAL ON COMPUTING 2024年第4期53卷 1002-1038页

作者： Arya, Sunil da Fonseca, Guilherme D. Mount, David M. Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Aix Marseille Univ Marseille France LIS Lab Marseille France Univ Maryland Dept Comp Sci College Pk MD USA Univ Maryland Inst Adv Comp Studies College Pk MD USA

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and epsilon > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an epsilon expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and epsilon-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the closest vector problem (CVP). It is known how to construct coverings of size nO(n)/epsilon (n 1)/2 for general convex bodies in Rn. In special cases, such as when the convex body is the l p unit ball, this bound has been improved to 2O(n)/epsilon(n 1)/2. This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative. We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter epsilon > 0, we show that there exists a polytope P consisting of 2O(n)/epsilon (n 1)/2 vertices (facets) such that K subset of P subset of K(1+epsilon). This bound is optimal in the worst case up to factors of 2O(n). (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + epsilon)-approximate CVP algorithm that works in any norm, with a running time of 2O(n)/epsilon (n 1)/2 up to polynomial factors in the input size, and we obtain the fastest (1 + epsilon)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors o

关键词： approximation algorithms high dimensional geometry convex coverings Banach- Mazur metric lattice algorithms closest vector problem

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Properties of S-AB Method With Diminishing Step-Size

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第5期69卷 3222-3229页

作者： Zhao, Shengchao Liu, Yongchao Dalian Univ Technol Sch Math Sci Dalian 116024 Peoples R China

The popular AB /push-pull method for distributed optimization problem may unify much of the existing decentralized first-order methods based on gradient tracking technique. More recently, the stochastic gradient variant of AB /push-pull method ( S - AB ) has been proposed, which achieves the linear rate of converging to a neighborhood of the global minimizer when the step-size is constant. This article is devoted to the asymptotic properties of S - AB with diminishing step-size. Specifically, under the condition that each local objective is smooth and the global objective is strongly convex, we first present the boundedness of the iterates of S - AB and then show that the iterates converge to the global minimizer with the rate O(1/k) in the mean square sense. Furthermore, the asymptotic normality of Polyak-Ruppert averaged S - AB is obtained and applications on statistical inference are discussed. Finally, numerical tests are conducted to demonstrate the theoretic results.

关键词： Convergence Optimization Covariance matrices Stochastic processes Linear programming Gaussian distribution approximation algorithms S-AB asymptotic normality convergence rate distributed stochastic optimization (DSO)

来源：评论

学校读者我要写书评

暂无评论

A Bifactor approximation Algorithm for Cloudlet Placement in Edge Computing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第8期33卷 1787-1798页

作者： Bhatta, Dixit Mashayekhy, Lena Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA

Emerging applications with low-latency requirements such as real-time analytics, immersive media applications, and intelligent virtual assistants have rendered Edge Computing as a critical computing infrastructure. Existing studies have explored the cloudlet placement problem in a homogeneous scenario with different goals such as latency minimization, load balancing, energy efficiency, and placement cost minimization. However, placing cloudlets in a highly heterogeneous deployment scenario considering the next-generation 5G networks and IoT applications is still an open challenge. The novel requirements of these applications indicate that there is still a gap in ensuring low-latency service guarantees when deploying cloudlets. Furthermore, deploying cloudlets in a cost-effective manner and ensuring full coverage for all users in edge computing are other critical conflicting issues. In this article, we address these issues by designing a bifactor approximation algorithm to solve the heterogeneous cloudlet placement problem to guarantee a bounded latency and placement cost, while fully mapping user applications to appropriate cloudlets. We first formulate the problem as a multi-objective integer programming model and show that it is a computationally NP-hard problem. We then propose a bifactor approximation algorithm, ACP, to tackle its intractability. We investigate the effectiveness of ACP by performing extensive theoretical analysis and experiments on multiple deployment scenarios based on New York City OpenData. We prove that ACP provides a (2,4)-approximation ratio for the latency and the placement cost. The experimental results show that ACP obtains near-optimal results in a polynomial running time making it suitable for both short-term and long-term cloudlet placement in heterogeneous deployment scenarios.

关键词： Cloud computing Costs approximation algorithms Edge computing Servers Low latency communication Internet of Things Edge computing cloudlets placement cost latency full coverage approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Empowering Random Walk Link Prediction algorithms in Complex Networks by Adapted Structural Information

引用

IEEE ACCESS 2024年 12卷 45044-45059页

作者： Dimitriou, Paraskevas Karyotis, Vasileios Ionian Univ Dept Informat Corfu 49100 Greece

In the link prediction problem a relevant algorithm running over a network attempts to determine whether a link between two nodes will exist in the future, given that it is not present at the moment. Most link prediction algorithms take into account the structure of the network on which they are applied and based on this, they attempt to predict the existence or not of future new edges in the network. However, many of them are quite standardized, applying the same concept and parametrization to all networks, thus not always achieving good results in every different network structure. algorithms based on Graph Neural Networks (GNNs) are more adaptive to any network structure but they do not give appreciable results when the only information available is the network structure. In this paper, we propose a new approach to this problem that approximates the structure of a complex network by allowing adjusted weight to this network structure to create additional information, which we can embed into effective algorithms such as local and superposed random walk link prediction. To achieve this goal, we use well-known kernel functions such as Sigmoids, in which we fit their parameters appropriately by a genetic algorithm to achieve the best possible approximation. To demonstrate the effectiveness of our proposed method we have compared our prediction method results based on precision, AUC and AUPR on eleven selected networks of different structures and properties with seven well-known link prediction algorithms and one more utilizing GNNs. In every case, we have improved the results of random walk algorithms and in most cases we achieved better results from all employed benchmark algorithms.

关键词： Prediction algorithms Complex networks Indexes Graph neural networks approximation algorithms Genetic algorithms Measurement link prediction node similarity sigmoid function genetic algorithms algorithm adaptation

来源：评论

学校读者我要写书评

暂无评论

A 43.9 μs IRS Controller SoC With Grid-Based Phase-Shift Optimization in 28 nm CMOS Technology for Next-Generation Communication

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2024年第7期71卷 3401-3412页

作者： Moon, Seungsik Lee, Youngjoo Pohang Univ Sci & Technol POSTECH Dept Elect Engn Pohang 37673 South Korea

Intelligent reflecting surface (IRS) is one of the promising technologies for next-generation communication systems. Although IRS can enhance the integrity of the transmitted signal, however, it requires additional phase-shift optimization task, potentially increasing the total processing latency of the system. To implement a phase-shift optimization algorithm with low-latency, for the world-first, IRS controller SoC for saving the base station (BS) transmit (TX) antenna power is presented with novel latency reduction techniques;1) grid-based phase-shift elements with a coarse-grained update, 2) quality-aware approximate processing element with low-resolution saturation arithmetic, 3) optimized data-flow scheduling with double-buffer architecture, and 4) novel low-latency weight update tracking technique. By adopting the proposed techniques, the fully-optimized SoC architecture can enhance the processing latency and energy consumption by 93% and 68%, respectively, compared with the unoptimized SoC architecture. The proposed system is designed and fabricated in 28 nm CMOS technology, where the implementation results show that the fully-optimized SoC system can achieve 43.9 mu of processing latency while saving 14.5 dB of TX antenna power for optimizing the 16x16 grid-based IRS architecture with 128 x 8 MU-MIMO configuration.

关键词： Optimization Computer architecture Linear programming Complexity theory approximation algorithms Vectors Low latency communication IRS controller MIMO phase-shift optimization

来源：评论

学校读者我要写书评

暂无评论

LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期206卷 239-281页

作者： El Housni, Omar Foussoul, Ayoub Goyal, Vineet Cornell Univ Operat Res & Informat Engn New York NY USA Columbia Univ Ind Engn & Operat Res New York NY 10027 USA

We consider the class of disjoint bilinear programs max {x(T) y | x is an element of X, y is an element of Y} where X and Y are packing polytopes. We present an O( log logm1 /logm1 log logm2/ logm2)-approximation algorithm for this problem where m1 and m2 are the number of packing constraints in X and Y respectively. In particular, we show that there exists a near-optimal solution ( (x) over tilde, (y) over tilde) such that (x) over tilde and (y) over tilde are "near-integral". We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an O( log n /log log n log L/ log log L)-approximation where L is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an O( log n log log n/ log L log log L)-approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.

关键词： Disjoint bilinear programming Two-stage robust optimization approximation algorithms RLT Affine policies

来源：评论

学校读者我要写书评

暂无评论

Fair Beam Allocations Through Reconfigurable Intelligent Surfaces

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2024年第11期42卷 3095-3109页

作者： Xiong, Rujing Yin, Ke Mi, Tiebin Lu, Jialong Wan, Kai Qiu, Robert Caiming Huazhong Univ Sci & Technol Sch Elect Informat & Commun Wuhan 430074 Peoples R China Huazhong Univ Sci & Technol Ctr Math Sci Wuhan 430074 Peoples R China

A fair beam allocation framework through reconfigurable intelligent surfaces (RISs) is proposed, incorporating the Max-min criterion. This framework focuses on designing explicit beamforming functionalities through optimization. Firstly, realistic models, grounded in geometrical optics, are introduced to characterize the input/output behaviors of RISs, effectively bridging the gap between the requirements on explicit beamforming operations and their practical implementations. Then, a highly efficient algorithm is developed for Max-min optimizations involving quadratic forms. Leveraging the Moreau-Yosida approximation, we successfully reformulate the original problem and propose an iterative algorithm to obtain the optimal solution. A comprehensive analysis of the algorithm's convergence is provided. Importantly, this approach exhibits excellent extensibility, making it readily applicable to address a broader class of Max-min optimization problems. Finally, numerical and prototype experiments are conducted to validate the effectiveness of the framework. With the proposed beam allocation framework and algorithm, we clarify that several crucial redistribution functionalities of RISs, such as explicit beam-splitting, fair beam allocation, and wide-beam generation, can be effectively implemented. These explicit beamforming functionalities have not been thoroughly examined previously.

关键词： Array signal processing Resource management Minimax techniques Optimization approximation algorithms Antenna arrays Reconfigurable intelligent surfaces Reconfigurable intelligent surface (RIS) fair beam allocation beam-splitting wide-beam generation max-min optimization Moreau-Yosida approximation prototype experiment

来源：评论

学校读者我要写书评

暂无评论

TDEC: Evidential Clustering Based on Transfer Learning and Deep Autoencoder

引用

IEEE TRANSACTIONS ON FUZZY SYSTEMS 2024年第10期32卷 5585-5597页

作者： Jiao, Lianmeng Wang, Feng Liu, Zhun-Ga Pan, Quan Northwestern Polytech Univ Sch Automat Xian 710072 Peoples R China

Evidential clustering is a promising clustering framework using Dempster-Shafer belief function theory to model uncertain data. However, evidential clustering needs to estimate more parameters compared with other clustering algorithms, and thus the clustering performance of evidential clustering will be greatly affected if data is insufficient or contaminated. In addition, the existing evidential clustering algorithms can not well deal with high-dimensional data such as texts and images. To solve the above problems, an evidential clustering algorithm based on transfer learning and deep autoencoder (TDEC) is proposed. The TDEC utilizes deep autoencoder to obtain evidential clustering-friendly representations of the original data, and applies the maximum mean discrepancy (MMD) constraint between the source network and the target network, so that the network can learn domain-invariant features. The algorithm jointly trains the deep evidential clustering networks in the source domain and the target domain, and realizes the deep feature representations of high-dimensional data in the target domain for evidential clustering by minimizing reconstruction loss, entropy-based evidential clustering loss, MMD loss and the regular penalty term of the network parameters. In addition, an iterative optimization method to solve the TDEC objective function is proposed. Extensive experiments were conducted to evaluate the clustering performance of the proposed TDEC algorithm compared with the existing shallow transfer clustering algorithms and deep clustering algorithms. For both image and text clustering tasks, the proposed TDEC achieved approximately 5% performance improvement over the comparison algorithms on average. In addition, the practical application value of the proposed TDEC algorithm was demonstrated in unsupervised remote sensing image scene classification.

关键词： Clustering algorithms Partitioning algorithms Transfer learning Evidence theory Feature extraction Fuzzy systems approximation algorithms Deep autoencoder evidential clustering unsupervised transfer learning

来源：评论

学校读者我要写书评

暂无评论

An Online Fairness-Aware Task Planning Approach for Spatial Crowdsourcing

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2024年第1期23卷 150-163页

作者： Zhang, Jiale Jiang, Tianxiang Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn MoE Key Lab Artificial Intelligence Shanghai 200240 Peoples R China

Spatial crowdsourcing, a human-centric paradigm for performing spatial tasks, has drawn rising attention. Task assignment and worker scheduling are basic issues in spatial crowdsourcing, which has a high demand on the timeliness of tasks and fairness among workers. In this article, we propose Utility-Fairness Index to evaluate the performance of the crowdsourcing platform and introduce the Fairness-Aware Task Planning problem that maximizes the utility while well-maintaining fairness during task assignment. We prove that its offline version is NP-hard, and clarify that there is no deterministic online algorithm with a constant competitive ratio for it. Two greedy-based online algorithms, Traversal Search and Advanced Nearest Neighbor are designed to solve the problem. We make optimization on running time with recurrence method to reach linear complexity, and use Gaussian Mixture Model to reveal the distribution regularity of tasks in these algorithms. Experiments on both synthetic and real datasets validate the efficiency and effectiveness of our algorithms.

关键词： Task analysis Crowdsourcing approximation algorithms Heuristic algorithms Optimization Indexes Planning Spatial crowdsourcing task assignment fairness NP-hardness greedy scheduling

来源：评论

学校读者我要写书评

暂无评论

Connected k-Center and k-Diameter Clustering

引用

ALGORITHMICA 2024年第11期86卷 3425-3464页

作者： Drexler, Lukas Eube, Jan Luo, Kelin Reineccius, Dorian Roeglin, Heiko Schmidt, Melanie Wargalla, Julian Heinrich Heine Univ Dusseldorf Dusseldorf Germany Univ Bonn Bonn Germany Univ Buffalo Buffalo NY USA

Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. The former problem has been introduced by Ge et al. (ACM Trans Knowl Discov Data 2(2):1-35, 2008. https://***/10.1145/1376815.1376816) to model clustering of data sets with both attribute and relationship data. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on the input points, and a clustering is now only feasible if every cluster induces a connected subgraph in G. Usually in clustering problems one assumes that the clusters are pairwise disjoint. We study this case but additionally also the case that clusters are allowed to be non-disjoint. This can help to satisfy the connectivity constraints. Our main result is an O(log(2) k)-approximation algorithm for the disjoint connected k-center and k-diameter problem. For Euclidean spaces of constant dimension and for metrics with constant doubling dimension, the approximation factor improves to O(1). Our algorithm works by computing a non-disjoint connected clustering first and transforming it into a disjoint connected clustering. We complement these upper bounds by several upper and lower bounds for variations and special cases of the model.

关键词： approximation algorithms Clustering Connectivity constraints

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：