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

26th International Conference on approximation algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

作者： Höhne, Felix van Stee, Rob Fraunhofer Institute for Industrial Mathematics ITWM Kaiserslautern Germany University of Siegen Germany

ISBN: (纸本)9783959772969

In the discrete bamboo garden trimming problem we are given n bamboo that grow at rates v1, . . ., vn per day. Each day a robotic gardener cuts down one bamboo to height 0. The goal is to find a schedule that minimizes the height of the tallest bamboo that ever exists. We present a 10/7-approximation algorithm that is based on a reduction to the pinwheel problem. This is consistent with the approach of earlier algorithms, but some new techniques are used that lead to a better approximation ratio. We also consider the continuous version of the problem where the gardener travels in a metric space between plants and cuts down a plant each time he reaches one. We show that on the star graph the previously proposed algorithm Reduce-Fastest is a 6-approximation and the known Deadline-Driven Strategy is a (3 + 2√2)-approximation. The Deadline-Driven Strategy is also a (9 + 2√5)-approximation on star graphs with multiple plants on each branch. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

S-NEAR-DGD: A Flexible Distributed Stochastic Gradient Method for Inexact Communication

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第2期68卷 1281-1287页

作者： Iakovidou, Charikleia Wei, Ermin Northwestern Univ Dept Elect & Comp Engn Evanston IL 60208 USA

We present and analyze a stochastic distributed method (S-NEAR-DGD) that can tolerate inexact computation and inaccurate information exchange to alleviate the problems of costly gradient evaluations and bandwidth-limited communication in large-scale systems. Our method is based on a class of flexible, distributed first-order algorithms that allow for the tradeoff of computation and communication to best accommodate the application setting. We assume that the information exchanged between nodes is subject to random distortion and that only stochastic approximations of the true gradients are available. Our theoretical results prove that the proposed algorithm converges linearly in expectation to a neighborhood of the optimal solution for strongly convex objective functions with Lipschitz gradients. We characterize the dependence of this neighborhood on algorithm and network parameters, the quality of the communication channel and the precision of the stochastic gradient approximations used. Finally, we provide numerical results to evaluate the empirical performance of our method.

关键词： Optimization Convergence Distributed algorithms Radio frequency approximation algorithms Quantization (signal) Probabilistic logic Distributed optimization network optimization quantization stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

Differential Evolution With Exponential Crossover: An Experimental Analysis on Numerical Optimization

引用

IEEE ACCESS 2023年 11卷 131677-131707页

作者： Li, Juncan Meng, Zhenyu Fujian Univ Technol Inst Artificial Intelligence Fuzhou 350118 Peoples R China

Since the inception in 1995, Differential Evolution (DE) has gained significant attention from researchers worldwide, and many DE variants proposed in the last decades obtained excellent performance in many scientific and engineering applications. However, the vast majority of these well-performed DE variants employ binomial crossover rather than exponential crossover in generating trial vector candidates though both of the two schemes were proposed simultaneously. That may be also the reason why there still doesn't exist such a thorough analysis of DE with exponential crossover. Different from the majority of DE researchers believing that DE variants with binomial crossover usually exhibit superior performance than the ones employing exponential crossover and DE variants with exponential crossover are good at tackling optimization problems with linkages among neighboring variables, we found that DE variants with exponential crossover can achieve competitive performance with the ones employing binomial crossover regardless of whether there are linkages among the variables or not after discovering the proper crossover rate $CR$ and its corresponding parameter control. In order to enrich research of DE on exponential crossover, this paper presents an thorough experimental analysis of DE algorithm with exponential crossover in numerical optimization, presenting the basic concepts of exponential crossover, giving the mathematical analysis why they can actually achieve similar optimization between exponential crossover and binomial crossover, experimental validation under the 100 benchmark functions from CEC2013, CEC2014, CEC2017, CEC2022 test suites as well as the tension/compression spring design problem, and summarizing and classifying various engineering applications that exponential crossover DEs are used to solve. Furthermore, we also look into the future challenges and potential directions for further development of DE with exponential crossover.

关键词： Statistics Social factors Optimization methods approximation algorithms Search problems Object recognition Next generation networking Differential equations Algorithm design and analysis Differential evolution exponential crossover binomial crossover algorithms validation

来源：评论

学校读者我要写书评

暂无评论

CAAM: Compressor-Based Adaptive Approximate Multiplier for Neural Network Applications

引用

IEEE EMBEDDED SYSTEMS LETTERS 2023年第3期15卷 117-120页

作者： Kumar, U. Anil Bharadwaj, S. Vignesh Pattaje, Avinash Bhat Nambi, Suresh Ahmed, Syed Ershad B V Raju Inst Technol ECE Dept Narsapur 502313 India Birla Inst Technol & Sci Pilani Dept Elect Engn Hyderabad 500078 India Birla Inst Technol & Sci Pilani Dept Elect Hyderabad 500078 India

Approximate computing is an evolving paradigm that aims to improve the power, speed, and area in neural network applications that can tolerate errors up to a specific limit. This letter proposes a new multiplier architecture based on the algorithm that adapts the approximate compressor from the existing and proposed compressors' set to reduce error in the respective partial product columns. Further, the error due to the approximation in the proposed multiplier is corrected using a simple error-correcting module. Results prove that the power and power-delay product (PDP) of an 8-bit multiplier is improved by up to 39.9% and 43.6% compared with the exact multiplier and 27.5% and 23.9% compared to similar previous designs. The proposed multiplier is validated using image processing and neural network applications to prove its efficacy.

关键词： approximation algorithms Image coding Neural networks Measurement Layout Computer architecture Adders Approximate computing Energy efficiency Embedded systems Approximate compressor approximate computing neural network application partial product reduction (PPR)

来源：评论

学校读者我要写书评

暂无评论

Robust Interferometric ISAR Imaging With UAMP-Based Joint Sparse Signal Recovery

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2023年第4期59卷 3890-3906页

作者： Kang, Hailong Li, Jun Guo, Qinghua Martorella, Marco Giusti, Elisa Cai, Jinjian Xidian Univ Hangzhou Inst Technol Hangzhou 311200 Peoples R China Xidian Univ Natl Lab Radar Signal Proc Xian 710071 Peoples R China Univ Wollongong Sch Elect Comp & Telecommun Engn Wollongong NSW 2522 Australia Natl Lab Radar & Surveillance Syst RaSS CNIT Pisa Italy Beijing Inst Technol Key Lab Elect & Informat Technol Satellite Nav Minist Educ Beijing 100081 Peoples R China Natl Lab Radar & Surveillance Syst CNIT I-56124 Pisa Italy

Sparse Bayesian learning (SBL) has found successful applications in interferometric inverse synthetic aperture radar (InISAR) imaging, especially in the presence of limited number of pulses or when using sparse apertures. SBL-based InISAR algorithms have been proven to be significantly superior to Fourier transform-based ones. However, the existing SBL-based algorithms are slow due to their high computational complexity. Moreover, there is also much room to improve in terms of imaging performance. In this article, leveraging the approximate message passing with unitary transformation (UAMP), we propose an InISAR imaging algorithm named UAMP joint sparse recovery (JSR), which is much faster and delivers notably higher imaging accuracy than the existing SBL-based algorithms. Specifically, we develop a type-2 joint sparse model for InISAR imaging and formulate it as a two-layer multiple measurement vectors joint sparse problem. Based on a factor graph representation, the message passing techniques are used to efficiently solve this problem, which leads to the UAMP-JSR algorithm. Results based on extensive simulations and experiments based on the real data collected by the Pisa Radar demonstrate the effectiveness and superiority of the proposed algorithm compared to existing algorithms.

关键词： Imaging Radar imaging approximation algorithms Three-dimensional displays Signal processing algorithms Antenna measurements Spaceborne radar Interferometric inverse synthetic aperture radar (InISAR) joint sparse recovery sparse Bayesian learning (SBL) unitary transformation (UAMP)

来源：评论

学校读者我要写书评

暂无评论

Optimal Low-Complexity Orthogonal Block Based Detection of OTFS for Low-Dispersion Channels

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第4期72卷 5419-5423页

作者： Liu, Wei Ding, Yajie Li, Chuan Hanzo, Lajos Xidian Univ State Key Labs Integrated Serv Networks Xian 710071 Peoples R China Xian Univ Posts & Telecommun Sch Comp & Technol Xian 710061 Peoples R China Univ Southampton Sch Elect & Comp Sci Southampton SO17 1BJ England

Orthogonal time frequency space (OTFS) modulation constitutes a promising technology for high-mobility scenarios. However, the detection of OTFS systems imposes substantial complexity. Hence, we propose a novel orthogonal block (OB) based detection scheme for significantly reducing the OTFS detection complexity without any performance loss with integer Doppler shifts. This is achieved by recognizing that the received signal can be partitioned into multiple parallel orthogonal blocks. Therefore, the detection of data symbols within an orthogonal block only depends on the signals received within this orthogonal block with reduced dimension. Explicitly, we propose a graph theory based orthogonal block identification algorithm, which models the relationship between the received signal and the original information symbols as a bipartite graph, where a depth first search (DFS) algorithm is invoked for partitioning the received signals into orthogonal blocks. For each orthogonal block, the existing detection algorithms can be used. Since the size of orthogonal blocks may be much lower than that of the original received signals, the detection complexity can be significantly reduced. For example, the complexity of the OB based MMSE detector is approximately a factor 4096 lower than that of the traditional MMSE detector for a channel having two paths.

关键词： Symbols Detectors Complexity theory Detection algorithms Delays Partitioning algorithms approximation algorithms Depth first search low complexity orthogonal block OTFS

来源：评论

学校读者我要写书评

暂无评论

An ϵ-approximation On-line Algorithm for Quantiles Based on Counters 14

An ϵ-Approximation On-line Algorithm for Quantiles Based on...

引用

14th IIAI International Congress on Advanced Applied Informatics, IIAI-AAI 2023

作者： Maeda, Kosuke Iwanuma, Koji University of Yamanashi Kofu-shi Japan

ISBN: (纸本)9798350324228

The quantiles are very important as a statistic that gives an overview of big data. In this paper, we study the GK algorithm for finding ϵ-approximate quantiles and point out its redundancy hidden the quantile summary. We introduce a counter mechanism and give a new approximation algorithm that is more space efficient. We theoretically guarantee that the maximum quantile error is within the range of the ϵ-approximation, and confirm by computational experiments that the spatial complexity required to preserve the ϵ-approximate quantile summary is significantly improved. © 2023 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Generalized Approximate Message Passing Based Bayesian Learning Detectors for Uplink Grant-Free NOMA

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第11期72卷 15057-15061页

作者： Zhang, Xiaoxu Fan, Pingzhi Hao, Li Quan, Xin Southwest Jiaotong Univ Chengdu 611756 Peoples R China

The existing sparse Bayesian learning (SBL) and pattern coupled sparse Bayesian learning (PCSBL) multiuser detection (MUD) algorithms for grant-free non-orthogonal multiple access (GF-NOMA) have high computational complexity, i.e. O(NK2), considering mainly the calculation of posterior distribution of the transmitted signals. In this paper, we embed generalized approximate message passing (GAMP) to SBL and PCSBL, and develop two efficient Bayesian learning algorithms for GF-NOMA systems, that is, generalized approximate message passing sparse Bayesian learning (GAMP-SBL) and generalized approximate message passing pattern coupled sparse Bayesian learning (GAMP-PCSBL). It is shown that the Bayesian algorithms can significantly reduce the computational complexity fromO(NK2) toO(NK). Simulation results show that these two low complexity detectors still have superior recovery performance than the conventional MUD methods, and nearly have the same performance compared with SBL and PCSBL.

关键词： Multiuser detection Bayes methods Uplink approximation algorithms Computational complexity Message passing NOMA GF-NOMA multiuser detection GAMP-SBL GAMP-PCSBL

来源：评论

学校读者我要写书评

暂无评论

Unconstrained traveling tournament problem is APX-complete

引用

OPERATIONS RESEARCH LETTERS 2023年第4期51卷 456-460页

作者： Bendayan, Salomon Cheriyan, Joseph Cheung, Kevin K. H. Univ Waterloo Dept Combinator & Optimizat 200 Univ Ave West Waterloo ON N2L 3G1 Canada Carleton Univ Sch Math & Stat 1125 Colonel Dr Ottawa ON K1S 5B6 Canada

We show that the Unconstrained Traveling Tournament Problem (UTTP) is APX-complete by giving an L-reduction from the following version of (1,2)-TSP: Given a complete graph on m nodes with edge costs of one or two, find a Hamiltonian cycle C that minimizes the objective m(m + 1) & sigma;{cost(ij) : ij & ISIN;C}. Our analysis gives an inapproximability threshold of 1 + ((& alpha;- 1)/200) for UTTP, where & alpha;denotes the inapproximability threshold for (1,2)-TSP.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Traveling tournament problem APX-complete approximation algorithms Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

A Multi-Objective Optimization Framework for Electric Vehicle Charge Scheduling With Adaptable Charging Ports

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第5期72卷 5702-5714页

作者： Mishra, Sanghamitra Mondal, Arijit Mondal, Samrat Indian Inst Technol Dept Comp Sci & Engn Patna 801106 India

The problem of charge scheduling of Electric Vehicles (EVs) at charging stations remains one of the significant challenges due to high charging time and insufficient charging infrastructure leading to unfulfilled demands. Moreover, most public charging stations (CSs) are equipped with charging ports that serve only a fixed charging rate. The installation of adaptable ports, that can vary their rate of charging with time, has been observed to alleviate these challenges. Hence, we propose an efficient EV charge scheduling plan, for a CS equipped with adaptable charging ports, to improve its performance. The CS aims at maximizing not only its profit but also its total customer satisfaction. Also, it is assumed that, upon being unable to fulfill their total energy demands, the CS pays an incentive to the EV owners. Such incentives reduce the profit margins of the CSs. Hence, we formulate a bi-objective optimization EV scheduling model that drives the CSs toward maximizing their profit and customer satisfaction. Satisfiability Modulo Theory (SMT) solver and Non-dominated Sorting Genetic Algorithm-II (NSGA-II) evolutionary algorithm are used to obtain the optimal and approximate Pareto fronts respectively. We further propose a charging action replacement-based heuristic approach to speed up the process of obtaining an approximate set of non-dominated solutions. We run several simulations and observe that the proposed algorithm results in a near-optimal set of solutions compared to the actual Pareto front with a much less computation time.

关键词： Charging stations Costs Customer satisfaction Scheduling approximation algorithms Pricing Processor scheduling Adaptable ports electric vehicles scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：