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

Assigning and Scheduling Generalized Malleable Jobs Under Subadditive or Submodular Processing Speeds

OPERATIONS RESEARCH 2024年第3期73卷 1598-1614页

作者： Fotakis, Dimitris Matuschke, Jannik Papadigenopoulos, Orestis Natl Tech Univ Athens Sch Elect & Comp Engn Athens 10682 Greece Katholieke Univ Leuven Res Ctr Operat Management B-3000 Leuven Belgium Columbia Univ Data Sci Inst New York NY 10027 USA

Malleable scheduling is a model that captures the possibility of parallelization to expedite the completion of time-critical tasks. A malleable job can be allocated and processed simultaneously on multiple machines, occupying the same time interval on all these machines. We study a general version of this setting, in which the functions determining the joint processing speed of machines for a given job follow different discrete concavity assumptions (subadditivity, fractional subadditivity, submodularity, and matroid ranks). We show that under these assumptions, the problem of scheduling malleable jobs at minimum makespan can be approximated by a considerably simpler assignment problem. Moreover, we provide efficient approximation algorithms for both the scheduling and the assignment problem, with increasingly stronger guarantees for increasingly stronger concavity assumptions, including a logarithmic approximation factor for the case of submodular processing speeds and a constant approximation factor when processing speeds are determined by matroid rank functions. Computational experiments indicate that our algorithms outperform the theoretical worst-case guarantees.

关键词： malleable scheduling makespan minimization approximation algorithms (fractional) subadditivity submodularity matroids

来源：评论

学校读者我要写书评

暂无评论

A Linear Time Algorithm for the Optimal Discrete IRS Beamforming

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2023年第3期12卷 496-500页

作者： Ren, Shuyi Shen, Kaiming Li, Xin Chen, Xin Luo, Zhi-Quan Chinese Univ Hong Kong Shenzhen Sch Sci & Engn Shenzhen 518172 Peoples R China Huawei Technol Xian 710075 Peoples R China Shenzhen Res Inst Big Data Shenzhen 518172 Peoples R China Chinese Univ Hong Kong Shenzhen Shenzhen 518172 Peoples R China

It remains an open problem to find the optimal configuration of phase shifts under the discrete constraint for intelligent reflecting surface (IRS) in polynomial time. The above problem is widely believed to be difficult because it is not linked to any known combinatorial problems that can be solved efficiently. The branch-and-bound algorithms and the approximation algorithms constitute the best results in this area. Nevertheless, this letter shows that the global optimum can actually be reached in linear time on average in terms of the number of reflective elements (REs) of IRS. The main idea is to geometrically interpret the discrete beamforming problem as choosing the optimal point on the unit circle. Although the number of possible combinations of phase shifts grows exponentially with the number of REs, it turns out that there are only a linear number of circular arcs that possibly contain the optimal point. Furthermore, the proposed algorithm can be viewed as a novel approach to a special case of the discrete quadratic program (QP).

关键词： Array signal processing Signal to noise ratio approximation algorithms Visualization Optimization Big Data Wireless communication Discrete beamforming for IRS RIS global optimum linear time algorithm discrete quadratic program

来源：评论

学校读者我要写书评

暂无评论

Joint Lifetime-Outage Optimization in Relay-Enabled IoT Networks-A Deep Reinforcement Learning Approach

引用

IEEE COMMUNICATIONS LETTERS 2023年第1期27卷 190-194页

作者： Heidarpour, Ali Reza Heidarpour, Mohammad Reza Ardakani, Masoud Tellambura, Chintha Uysal, Murat Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 1H9 Canada Isfahan Univ Technol Dept Elect & Comp Engn Esfahan *** Iran Ozyegin Univ Dept Elect & Elect Engn TR-34794 Istanbul Turkiye

Network lifetime maximization in Internet of things (IoT) is of paramount importance to ensure uninterrupted data transmission and reduce the frequency of battery replacement. This letter deals with the joint lifetime-outage optimization in relay-enabled IoT networks employing a multiple relay selection (MRS) scheme. The considered MRS problem is essentially a general nonlinear 0-1 programming which is NP-hard. In this work, we use the application of the double deep Q network (DDQN) algorithm to solve the MRS problem. Our results reveal that the proposed DDQN-MRS scheme can achieve superior performance than the benchmark MRS schemes.

关键词： Relays Q-learning Protocols Mathematical models approximation algorithms Training Internet of Things cooperative communication multiple relay selection deep reinforcement learning lifetime

来源：评论

学校读者我要写书评

暂无评论

Single machine robust scheduling with budgeted uncertainty

引用

OPERATIONS RESEARCH LETTERS 2023年第2期51卷 137-141页

作者： Bougeret, Marin Pessoa, Artur Poss, Michael Univ Montpellier LIRMM CNRS Rue Ada 156 F-34095 Montpellier France Univ Fed Fluminense Prod Engn Dept Rua Passo Patria 156309-D BR-24210240 Niteroi Brazil

We consider robust single machine scheduling problems. First, we prove that with uncertain processing times, minimizing the number of tardy jobs is NP-hard. Second, we show that the weighted variant of the problem has the same complexity as the nominal counterpart whenever only the weights are uncertain. Last, we provide approximation algorithms for the problems minimizing the weighted sum of completion times. Noticeably, our algorithms extend to more general robust combinatorial optimization problems with cost uncertainty, such as max-cut.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Robust scheduling NP-hardness approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Recursive Least Squares-Algorithm-Based Normalized Adaptive Minimum Symbol Error Rate Equalizer

引用

IEEE COMMUNICATIONS LETTERS 2023年第1期27卷 317-321页

作者： Zhang, Minhao Wang, Yifan Tu, Xingbin Qu, Fengzhong Zhao, Hangfang Zhejiang Univ Key Lab Ocean Observat Imaging Testbed Zhejiang Pr Zhoushan 316021 Peoples R China Minist Educ Engn Res Ctr Ocean Sensing Technol & Equipment Zhoushan 316021 Peoples R China Zhejiang Univ Hainan Inst Sanya 572025 Peoples R China

The adaptive minimum symbol error rate (AMSER) equalizer is known to have better symbol error rate (SER) performance than the adaptive minimum mean square error equalizer. Furthermore, the normalized AMSER (NAMSER) equalizer outperforms the AMSER equalizer, which can be regarded as the improvement of the normalized least mean square (NLMS) equalizer by incorporating the minimum SER (MSER) criterion. Inspired by that, we propose an improved recursive least squares-based NAMSER equalizer (RLS-NAMSER) that takes the advantage of faster convergence of the RLS algorithm over the NLMS algorithm. The RLS algorithm is first reconsidered from the perspective of optimization problem and an approximate RLS (ARLS) algorithm is proposed which converges faster than the NLMS algorithm. The RLS-NAMSER equalizer is then proposed by combining the ARLS equalizer with the MSER criterion. Simulation results show that the RLS-NAMSER equalizer has better convergence performance than the NAMSER equalizer while having nearly the same steady state performance as the NAMSER equalizer.

关键词： Equalizers Optimization Symbols approximation algorithms Quadrature amplitude modulation Convergence Binary phase shift keying Adaptive equalizers minimum symbol error rate constrained optimization recursive least squares

来源：评论

学校读者我要写书评

暂无评论

Dynamic Orthogonal Matching Pursuit for Sparse Data Reconstruction

IEEE OPEN JOURNAL OF SIGNAL PROCESSING

引用

IEEE OPEN JOURNAL OF SIGNAL PROCESSING 2023年 4卷 242-256页

作者： Zhao, Yun-Bin Luo, Zhi-Quan Chinese Univ Hong Kong Shenzhen Res Inst Big Data Shenzhen 518172 Peoples R China

The orthogonal matching pursuit (OMP) is one of the mainstream algorithms for sparse data reconstruction or approximation. It acts as a driving force for the development of several other greedy methods for sparse data reconstruction, and it also plays a vital role in the development of compressed sensing theory for sparse signal and image reconstruction. In this article, we propose the so-called dynamic orthogonal matching pursuit (DOMP) and enhanced dynamic orthogonal matching pursuit (EDOMP) algorithms which are more efficient than OMP for sparse data reconstruction from a numerical point of view. We carry out a rigorous analysis to establish the reconstruction error bound for DOMP under the restricted isometry property of the measurement matrix. The main result claims that the reconstruction error via DOMP can be controlled and measured in terms of the number of iterations, sparsity level of data, and the noise level of measurements. Moveover, the finite convergence of DOMP for a class of large-scale compressed sensing problems is also shown.

关键词： Matching pursuit algorithms Signal processing algorithms Image reconstruction Indexes Heuristic algorithms Measurement uncertainty approximation algorithms Data reconstruction dynamic orthogonal matching pursuit error bound orthogonal matching pursuit restricted isometry property sparse optimization

来源：评论

学校读者我要写书评

暂无评论

An Iterative Random Sampling Algorithm for Rapid and Scalable Estimation of Matrix Spectra

引用

IEEE JOURNAL ON MULTISCALE AND MULTIPHYSICS COMPUTATIONAL TECHNIQUES 2023年 8卷 205-216页

作者： Kelley, Jon T. Yilmaz, Ali E. Brick, Yaniv Univ Texas Austin Oden Inst Computat Engn & Sci Austin TX 78712 USA Ben Gurion Univ Negev Sch Elect & Comp Engn IL-8410501 Beer Sheva Israel

An easy-to-implement iterative algorithm that enables efficient and scalable spectral analysis of dense matrices is presented. The algorithm relies on the approximation of a matrix's singular values by those of a series of smaller matrices formed from uniform random sampling of its rows and columns. It is shown that, for sufficiently incoherent and rank-deficient matrices, the singular values [are expected to] decay at the same rate as those of matrices formed via this sampling scheme, which permits such matrices' ranks to be accurately estimated from the smaller matrices' spec-tra. Moreover, for such a matrix of size m x n, it is shown that the dominant singular values are [expected to be] root mn/k times those of a k x k matrix formed by randomly sampling k of its rows and columns. Starting from a small initial guess k = k(0), the algorithm repeatedly doubles k until two convergence criteria are met;the criteria to ensure that k is sufficiently large to estimate the singular values, to the desired accuracy, are presented. The algorithm's properties are analyzed theoretically and its efficacy is studied numerically for small to very-large matrices that result from discretization of integral-equation operators, with various physical kernels common in electromagnetics and acoustics, as well as for artificial matrices of various incoherence and rank-deficiency properties.

关键词： approximation algorithms Matrix decomposition Classification algorithms Kernel Convergence Spectral analysis Estimation Integral equations low-rank approximations randomized algorithms rank revealing

来源：评论

学校读者我要写书评

暂无评论

An Experimental Evaluation of Semidefinite Programming and Spectral algorithms for Max Cut

引用

ACM Journal of Experimental Algorithmics 2023年第3期28卷 1-18页

作者： Mirka, Renee Williamson, David P. Cornell University IthacaNY14850 United States

We experimentally evaluate the performance of several Max Cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan's algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy Max Cut algorithm which has a .5 approximation guarantee, two additional spectral algorithms, and a heuristic from Burer, Monteiro, and Zhang (BMZ). The algorithms are tested on ErdÅ's-Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms and BMZ heuristic return cuts with values which are competitive with those of the SDP. © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sequential Diversification with Provable Guarantees 25

Sequential Diversification with Provable Guarantees

引用

18th International Conference on Web Search and Data Mining-WSDM

作者： Wang, Honglian Tu, Sijing Gionis, Aristides KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9798400713293

Diversification is a useful tool for exploring large collections of information items. It has been used to reduce redundancy and cover multiple perspectives in information-search settings. Diversification finds applications in many different domains, including presenting search results of information-retrieval systems and selecting suggestions for recommender systems. Interestingly, existing measures of diversity are defined over sets of items, rather than evaluating sequences of items. This design choice comes in contrast with commonly-used relevance measures, which are distinctly defined over sequences of items, taking into account the ranking of items. The importance of employing sequential measures is that information items are almost always presented in a sequential manner, and during their information-exploration activity users tend to prioritize items with higher ranking. In this paper, we study the problem of maximizing sequential diversity. This is a new measure of diversity, which accounts for the ranking of the items, and incorporates item relevance and user behavior. The overarching framework can be instantiated with different diversity measures, and here we consider the measures of sum diversity and coverage diversity. The problem was recently proposed by Coppolillo et al. [11], where they introduce empirical methods that work well in practice. Our paper is a theoretical treatment of the problem: we establish the problem hardness and present algorithms with constant approximation guarantees for both diversity measures we consider. Experimentally, we demonstrate that our methods are competitive against strong baselines.

关键词： Diversification Ranking algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Throughput Maximization in Wireless Networks With Delay Constraints

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2013年第6期21卷 1988-2000页

作者： Pei, Guanhong Parthasarathy, Srinivasan Srinivasan, Aravind Vullikanti, Anil Kumar S. Virginia Tech Dept Elect & Comp Engn Blacksburg VA 24061 USA Virginia Tech Virginia Bioinformat Inst Blacksburg VA 24061 USA IBM TJ Watson Res Ctr Hawthorne NY 10532 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA

We study the problem of throughput maximization in multihop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Delta(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O(log Delta(m)/ log log Delta(m)) of the maximum, so that the per-session (end-to-end) delay is, O(((log Delta(m)/ log log Delta(m))Delta(c))(2)) where Delta(m) = max(c){Delta(c)};note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.

关键词： approximation algorithms cross-layer design end-to-end delay optimization throughput

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：