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

A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource

引用

JOURNAL OF SCHEDULING 2021年第3期24卷 259-267页

作者： Hashimoto, Susumu Mizuno, Shinji Tokyo Inst Technol Dept Ind Engn & Econ Meguro Ku Tokyo Japan

In this paper, we investigate an open problem by Gyorgyi and Kis for a single-machine scheduling problem with a non-renewable resource (NR-SSP) and total weighted completion time criterion. The problem is NP-hard, even if every job has the same processing time, and each weight is equal to its required amount of the resource. Gyorgyi and Kis prove that a simple list scheduling algorithm for this special case is a 3-approximation algorithm and conjecture that the algorithm for the case is a 2-approximation algorithm. We prove their conjecture. More strongly, we show that the approximation ratio is strictly less than 2 for any instance, and for any epsilon>0, there exists an instance for which the approximation ratio is more than 2-epsilon.

关键词： Single-machine scheduling problems Non-renewable resources List scheduling algorithm approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Sequential Algorithm for Jerk Limited Speed Planning

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2022年第4期19卷 3192-3209页

作者： Consolini, Luca Locatelli, Marco Minari, Andrea Univ Parma Dipartimento Ingn & Architettura I-43124 Parma Italy

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments.

关键词： Planning Linear programming Optimization Heuristic algorithms Task analysis approximation algorithms Vehicle dynamics Optimization sequential line-search method speed planning

来源：评论

学校读者我要写书评

暂无评论

Parallel Dynamic Sparse Approximate Inverse Preconditioning Algorithm on GPU

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第12期33卷 4723-4737页

作者： Gao, Jiaquan Chu, Xinyue Wu, Xiaotong Wang, Jun He, Guixia Nanjing Normal Univ Sch Comp & Elect Informat Nanjing 210023 Peoples R China Futurewei Technol Santa Clara CA 95050 USA Zhejiang Univ Technol Zhijiang Coll Hangzhou 310023 Peoples R China

The dynamic sparse approximate inverse (SPAI) preconditioner has proven to be effective in accelerating the convergence of iterative methods for large linear systems. Recently, accelerating it on graphics processing unit (GPU) has attracted considerable attention due to the fact that the cost of constructing the preconditioner is high. However, the existing parallel dynamic SPAI preconditioning algorithms on GPU are usually ineffective because of the out-of-memory error for large matrices. This motivates us to investigate how to accelerate the construction of dynamic SPAI preconditioners on GPU. In this article, we propose an efficient dynamic SPAI preconditioning algorithm on GPU, called GDSPAI. For our proposed GDSPAI, there are the following novelties: (1) a well-known dynamic SPAI preconditioning algorithm is substantially modified to address the main challenges of parallelization on GPU, (2) a parallel framework of constructing the dynamic SPAI preconditioner on GPU is presented on the basis of the modified dynamic SPAI preconditioning algorithm;and (3) each component of the preconditioner is computed in parallel inside a group of threads. Experimental results show that the proposed GDSPAI is effective for large matrices, and outperforms the popular preconditioning algorithms in three public libraries, as well as a recent parallel static SPAI preconditioning algorithm.

关键词： Heuristic algorithms Graphics processing units Sparse matrices approximation algorithms Message systems Symmetric matrices Libraries Sparse approximate inverse preconditioning dynamic CUDA GPU

来源：评论

学校读者我要写书评

暂无评论

Distributed Kalman Filtering Through Trace Proximity

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第9期67卷 4908-4915页

作者： Liu, Wei Shi, Peng Wang, Shuoyu Zhejiang Gongshang Univ Sch Informat & Elect Engn Hangzhou 310018 Peoples R China Kochi Univ Technol Res Inst Kochi 7828502 Japan Univ Adelaide Sch Elect & Elect Engn Adelaide SA 5005 Australia Kochi Univ Technol Sch Syst Engn Kochi 7828502 Japan

This article is concerned with the distributed Kalman filtering problem for discrete-time linear systems whose measurement information comes from a set of sensor nodes that can communicate with their direct neighbors. Two algorithms for distributed Kalman filtering are proposed, where the first algorithm is based on single-node measurement and the second algorithm is based on neighboring-node measurements. In order to improve the performance, a novel criterion is introduced to the algorithm design, where in the criterion, the proximity of matrix's trace is used to determine the proximity of positive semidefinite matrix. We prove that all the proposed algorithms for distributed Kalman filtering are unbiased. Numerical examples are provided to demonstrate the correctness of the proposed theoretical method and the performance of the proposed new design technique.

关键词： Kalman filters Heuristic algorithms approximation algorithms Linear systems Weight measurement Symmetric matrices Noise measurement Discrete-time linear systems distributed Kalman filtering sensor networks trace unbiasedness

来源：评论

学校读者我要写书评

暂无评论

Approximating Multistage Matching Problems

引用

ALGORITHMICA 2022年第8期84卷 2135-2153页

作者： Chimani, Markus Troost, Niklas Wiedera, Tilo Osnabruck Univ Theoret Comp Sci Osnabruck Germany

In multistage perfect matching problems, we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight approximation on graph sequences of length two (2-stage graphs). On the other hand, we propose several general methods to deduce multistage approximations from blackbox approximations on 2-stage graphs.

关键词： Temporal graphs approximation algorithms Perfect matchings

来源：评论

学校读者我要写书评

暂无评论

Generalized Approximate Message Passing Equalization for Multi-Carrier Faster-Than-Nyquist Signaling

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2022年第3期71卷 3309-3314页

作者： Ma, Yunsi Wu, Nan Zhang, J. Andrew Li, Bin Hanzo, Lajos Beijing Inst Technol Sch Informat & Elect Beijing 100081 Peoples R China Univ Technol Sydney Sch Elect & Data Engn Global Big Data Technol Ctr Sydney NSW 2007 Australia Univ Southampton Sch Elect & Comp Sci Southampton SO17 1BJ Hants England

Multi-carrier faster-than-Nyquist (MFTN) signaling constitutes a promising spectrally efficient non-orthogonal physical layer waveform. In this correspondence, we propose a pair of low-complexity generalized approximate message passing (GAMP)-based frequency-domain equalization (FDE) algorithms for MFTN systems operating in multipath channels. To mitigate the ill-condition of the resultant equivalent channel matrix, we construct block circulant interference matrices by inserting a few cyclic postfixes, followed by truncating the duration of the inherent two-dimensional interferences. Based on the decomposition of the block circulant matrices, we develop a novel frequency-domain received signal model using the two-dimensional fast Fourier transform for mitigating the colored noise imposed by the non-orthogonal matched filter. Moreover, we derive a GAMP-based FDE algorithm and its refined version, where the latter relies on approximations for circumventing the emergence of the ill-conditioned matrices. Our simulation results demonstrate that, for a fixed spectral efficiency, MFTN signaling can significantly improve the bit error rate (BER) performance by jointly optimizing the time- and frequency-domain packing factors. Compared to its Nyquist-signaling counterpart, our proposed MFTN systems employing the refined GAMP equalizer can achieve about 39% higher transmission rates at a negligible BER performance degradation.

关键词： Receivers Complexity theory Time-frequency analysis Bit error rate approximation algorithms Equalizers Colored noise Block circulant matrix with circulant blocks frequency-domain equalization generalized approximate message passing multi-carrier faster-than-Nyquist signaling

来源：评论

学校读者我要写书评

暂无评论

PARAMETERIZED approximation SCHEMES FOR STEINER TREES WITH SMALL NUMBER OF STEINER VERTICES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第1期35卷 546-574页

作者： Dvorak, Pavel Feldmann, Andreas E. Knop, Dusan Masarik, Tomas Toufar, Tomas Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague 11800 Czech Republic Charles Univ Prague Dept Appl Math Prague 11800 Czech Republic Czech Tech Univ Fac Informat Technol Prague 16000 Czech Republic Univ Warsaw Fac Math Informat & Mech PL-02097 Warsaw Poland Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an EPAS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree, but a PSAKS does not. We also prove that there is an EPAS and a PSAKS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.

关键词： Steiner tree Steiner forest approximation algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Study of Using Bethe/Kikuchi approximation for Learning Directed Graphic Models

引用

IEEE ACCESS 2021年 9卷 125428-125438页

作者： Lin, Peng Neil, Martin Fenton, Norman Capital Univ Econ & Business Sch Stat Beijing 100070 Peoples R China Queen Mary Univ London Sch Elect Engn & Comp Sci London E1 4NS England Agena Ltd Cambridge CB23 7NU England

This paper applies the variational methods to learn the parameters and the probability of evidence of directed graphic models (also known as Bayesian networks (BNs)) when data contains missing values. One class of variational methods, the Bethe/Kikuchi approximate algorithm, is combined with Expectation-Maximization (EM) to learn BN model parameters from data using an upper limit on cluster size. Our proposed method is novel since the Bethe/Kikuchi algorithms are typically only used to approximate marginal distributions. We review popular Bethe/Kikuchi approximate algorithms, including Belief Propagation (BP), Iterative Join Graph Propagation (IJGP), and Fundamental Cycle Base (FCB) algorithms for discrete BNs, and conduct experiments to test their learning performance using a wide range of discrete BNs in practice. Experiments show that by using IJGP or FCB algorithms, with EM, we can obtain more accurate results than the conventional approximate algorithms, such as Evidence Pre-propagation Importance Sampling and Variational Inference. When exact methods are intractable the IJGP/FCB with EM can be an effective alternative solution.

关键词： Inference algorithms approximation algorithms Clustering algorithms Partitioning algorithms Data structures Data models Graphics Bayesian networks Bethe Kikuchi empirical data EM algorithm generalized belief propagation parameter learning

来源：评论

学校读者我要写书评

暂无评论

A NEAR-LINEAR approximation SCHEME FOR MULTICUTS OF EMBEDDED GRAPHS WITH A FIXED NUMBER OF TERMINALS

引用

SIAM JOURNAL ON COMPUTING 2021年第1期50卷 1-31页

作者： Cohen-Addad, Vincent de Verdiere, Eric Colin de Mesmay, Arnaud Univ Paris 06 LIP6 CNRS Sorbonne UnivUPMC F-06 Paris France Univ Gustave Eiffel LIGM CNRS ESIEE Paris F-77454 Marne La Vallee France

For an undirected edge-weighted graph G and a set R of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from G disconnects each pair in R. We provide an algorithm computing a (1+epsilon)-approximation of the minimum multicut of a graph G in time (g+t)((O(g+t)3)) center dot(1/epsilon)(O(g+t)) center dot n log n, where g is the genus of G and t is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when g = 0). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces. Interestingly, such topological techniques seem necessary even for the planar case. We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight toward our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which G is embedded.

关键词： multicut graphs on surfaces topology approximation algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Algorithm Unrolling for Massive Access via Deep Neural Networks With Theoretical Guarantee

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第2期21卷 945-959页

作者： Shi, Yandong Choi, Hayoung Shi, Yuanming Zhou, Yong ShanghaiTech Univ Sch Informat Sci & Technol Shanghai 201210 Peoples R China Chinese Acad Sci Shanghai Inst Microsyst & Informat Technol Shanghai 200050 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Kyungpook Natl Univ Dept Math Daegu 41566 South Korea Yoke Intelligence Shanghai 201210 Peoples R China

Massive access is a critical design challenge of Internet of Things (IoT) networks. In this paper, we consider the grant-free uplink transmission of an IoT network with a multiple-antenna base station (BS) and a large number of single-antenna IoT devices. Taking into account the sporadic nature of IoT devices, we formulate the joint activity detection and channel estimation (JADCE) problem as a group-sparse matrix estimation problem. This problem can be solved by applying the existing compressed sensing techniques, which however either suffer from high computational complexities or lack of algorithm robustness. To this end, we propose a novel algorithm unrolling framework based on the deep neural network to simultaneously achieve low computational complexity and high robustness for solving the JADCE problem. Specifically, we map the original iterative shrinkage thresholding algorithm (ISTA) into an unrolled recurrent neural network (RNN), thereby improving the convergence rate and computational efficiency through end-to-end training. Moreover, the proposed algorithm unrolling approach inherits the structure and domain knowledge of the ISTA, thereby maintaining the algorithm robustness, which can handle non-Gaussian preamble sequence matrix in massive access. With rigorous theoretical analysis, we further simplify the unrolled network structure by reducing the redundant training parameters. Furthermore, we prove that the simplified unrolled deep neural network structures enjoy a linear convergence rate. Extensive simulations based on various preamble signatures show that the proposed unrolled networks outperform the existing methods in terms of the convergence rate, robustness and estimation accuracy.

关键词： Deep learning Convergence Estimation Training Robustness Internet of Things approximation algorithms Massive access joint activity detection and channel estimation group-sparse matrix estimation algorithm unrolling deep learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：