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

29th International Conference on Parallel and Distributed Computing (Euro-Par)

作者： Kanas, Tomasz Rzadca, Krzysztof Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9783031396977;9783031396984

A cloud scheduler packs tasks onto machines with contradictory goals of (1) using the machines as efficiently as possible while (2) avoiding overloading that might result in CPU throttling or out-of-memory errors. We take a stochastic approach that models the uncertainty of tasks' resource requirements by random variables. We focus on a little-explored case of items, each having a Bernoulli distribution that corresponds to tasks that are either idle or need a certain CPU share. RPAP, our online approximation algorithm, upper-bounds a subset of items by Poisson distributions. Unlike existing algorithms for Bernoulli items that prove the approximation ratio only up to a multiplicative constant, we provide a closed-form expression. We derive RPAPC, a combined approach having the same theoretical guarantees as RPAP. In simulations, RPAPC's results are close to FFR, a greedy heuristic with no worst-case guarantees;RPAPC slightly outperforms FFR on datasets with small items.

关键词： cloud scheduling stochastic bin packing stochastic optimization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Pandora Box Problem with Nonobligatory Inspection: Hardness and approximation Scheme 2023

Pandora Box Problem with Nonobligatory Inspection: Hardness ...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Fu, Hu Li, Jiawei Liu, Daogao Shanghai Univ Finance & Econ ITCS Shanghai Peoples R China Univ Texas Austin Austin TX USA Univ Washington Seattle WA USA

ISBN: (纸本)9781450399135

Weitzman (1979) introduced the Pandora Box problem as a model for sequential search with inspection costs, and gave an elegant index-based policy that attains provably optimal expected payoff. In various scenarios, the searching agent may select an option without making a costly inspection. The variant of the Pandora box problem with non-obligatory inspection has attracted interest from both economics and algorithms researchers. Various simple algorithms have proved suboptimal, with the best known 0.8-approximation algorithm due to Guha et al. (2008). No hardness result for the problem was known. In this work, we show that it is NP-hard to compute an optimal policy for Pandora's problem with nonobligatory inspection. We also give a polynomial-time approximation scheme (PTAS) that computes policies with an expected payoff at least (1 - epsilon)-fraction of the optimal, for arbitrarily small epsilon > 0. On the side, we show the decision version of the problem to be in NP.

关键词： Pandora box NP-hardness online algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Improving Netlist Transformation-Based Approximate Logic Synthesis Through Resynthesis

引用

IEEE EMBEDDED SYSTEMS LETTERS 2024年第3期16卷 279-282页

作者： Morales-Monge, Roger Castro-Godinez, Jorge Paim, Guilherme Sch Elect Engn Inst Tecnol Costa Rica Cartago 30101 Costa Rica Inst Engn Sistemas & Comp Invest & Desenvolvimento High Performance Comp Architecturesand Syst Res Gr P-1000029 Lisbon Portugal Univ Lisbon Inst Super Tecn P-1649004 Lisbon Portugal

To address the challenges of efficient hardware design for error-tolerant applications, several techniques of applied approximate computing have been proposed. Pruning algorithms aim to approximate circuits with reduced design requirements at the cost of an acceptable degradation of their quality of result. In this letter, we present the effects of resynthesis, an iterative application of logic synthesis along with pruning algorithms, into a state-of-the-art approximate design flow, AxLS. Resynthesis strategy improves the approximation, achieving up to 70% area-power savings for the same error in the output, and reducing the number of iterations, and hence the time required to explore the design space in up to $30\times $ , to obtain an approximated design.

关键词： Measurement Space exploration Logic gates Probabilistic logic approximation algorithms Optimization Hardware Approximate computing (AxC) circuit design electronic design automation (EDA) pruning

来源：评论

学校读者我要写书评

暂无评论

Average Consensus With Error Correction

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 115-120页

作者： Benalcazar, Diego R. Magnusson, Sindri Enyioha, Chinwendu Univ Cent Florida Elect & Comp Engn Dept Orlando FL 32816 USA Stockholm Univ Dept Comp & Syst Sci S-16407 Stockholm Sweden

We propose a novel method for achieving the average consensus in a distributed manner while dealing with communication compression. While it is widely recognized that distributed consensus algorithms with compression can falter due to compression-error-induced divergences, our approach integrates an error correction step to guarantee convergence towards an approximate average consensus across any bounded compression function. Significantly, with our error correction mechanism, we can achieve convergence to a solution of arbitrarily high accuracy, irrespective of how crude the compression is in a fully distributed setting. Additionally, we quantify the convergence rate and provide upper bounds for the estimation error based on the spectral properties of the underlying communication network. Simulation results validate the scalability and efficacy of our proposed algorithm.

关键词： Convergence Error correction Topology Upper bound Quantization (signal) Network topology approximation algorithms Quantized systems estimation sensor fusion

来源：评论

学校读者我要写书评

暂无评论

Low Cost Variable Step-Size LMS With Maximum Similarity to the Affine Projection Algorithm

IEEE OPEN JOURNAL OF SIGNAL PROCESSING

引用

IEEE OPEN JOURNAL OF SIGNAL PROCESSING 2024年 5卷 82-91页

作者： Ferrer, Miguel De Diego, Maria Gonzalez, Alberto Univ Politecn Valencia UPV Inst Telecommun & Multimedia Applicat iTEAM Valencia 46022 Spain

The LMS algorithm is widely employed in adaptive systems due to its robustness, simplicity, and reasonable performance. However, it is well known that this algorithm suffers from a slow convergence speed when dealing with colored reference signals. Numerous variants and alternative algorithms have been proposed to address this issue, though all of them entail an increase in computational cost. Among the proposed alternatives, the affine projection algorithm stands out. This algorithm has the peculiarity of starting from $N$ data vectors of the reference signal. It transforms these vectors into as many data vectors suitably normalized in energy and mutually orthogonal. In this work, we propose a version of the LMS algorithm that, similar to the affine projection algorithm, starts from $N$ data vectors of the reference signal but corrects them by using only a scalar factor that functions as a convergence step. Our goal is to align the behavior of this algorithm with the behavior of the affine projection algorithm without significantly increasing the computational cost of the LMS.

关键词： Signal processing algorithms Convergence Projection algorithms Computational efficiency approximation algorithms Costs Robustness Adaptive filters affine projection algorithm variable step-size

来源：评论

学校读者我要写书评

暂无评论

CGEDN: approximation of Graph Edit Distance with Path Generation via Learning Node Matching

CGEDN: Approximation of Graph Edit Distance with Path Genera...

引用

2025 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2025

作者： Yang, Liu Zheng, Qiankun Wang, Zidong School of Computer Science and Engineering Central South University Changsha China

ISBN: (纸本)9798350368741

Graph Edit Distance (GED) is a classical graph similarity metric. Since exact GED computation is NP-hard, existing GNN-based methods try to approximate GED in polynomial time. However, they still lack support for edge labels or the ability to generate an edit path. To address these limitations, we propose a hybrid method named CGEDN based on Graph Neural Networks and learnable node matching. Specifically, CGEDN starts with cross-graph feature aggregation layers, which generate node embeddings with fine-grained interaction features and support edge labels as well. Next, two node matching pipelines are applied to obtain a node matching confidence matrix and a cost matrix, where the confidence matrix is supervised by optimal node matchings corresponding to GED. Finally, we calculate the weighted sum of the cost matrix with a bias value to regress GED only, or search for the top-k most promising node matchings based on confidence matrix to approximate GED and recover an edit path simultaneously. The experimental results on real and synthetic graphs demonstrate that CGEDN significantly outperforms the best result of existing approximate methods. © 2025 IEEE.

关键词： approximation algorithms Graph Edit Distance Graph Neural Networks Graph Similarity

来源：评论

学校读者我要写书评

暂无评论

A general approximation for multistage subgraph problems 12

A general approximation for multistage subgraph problems

引用

12th Latin-American algorithms, Graphs and Optimization Symposium (LAGOS)

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

Subgraph Problems are optimization problems on graphs where a solution is a subgraph that satisfies some property and optimizes some measure. Examples include shortest path, minimum cut, maximum matching, or vertex cover. In reality, however, one often deals with time-dependent data, i.e., the input graph may change over time and we need to adapt our solution accordingly. We are interested in guaranteeing optimal solutions after each graph change while retaining as much of the previous solution as possible. Even if the subgraph problem itself is polynomial-time computable, this multistage variant turns out to be NP-hard in most cases. We present an algorithmic framework thatfor any subgraph problem of a certain typeguarantees an optimal solution for each point in time and provides an approximation guarantee for the similarity between subsequent solutions. We show that the class of applicable multistage subgraph problems is very rich and that proving membership to this class is mostly straightforward. As examples, we explicitly state these proofs and obtain corresponding approximation algorithms for the natural multistage versions of Shortest s-t-Path, Perfect Matching, Minimum s-t-Cutand further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, and Independent Set. We also report that all these problems are already NP-hard on only two stages. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： Multistage Graphs approximation algorithms approximation Framework Subgraph Optimization

来源：评论

学校读者我要写书评

暂无评论

Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function approximation 37

Finite-Time Analysis of Whittle Index based Q-Learning for R...

引用

37th Conference on Neural Information Processing Systems (NeurIPS)

作者： Xiong, Guojun Li, Jian SUNY Stony Brook Stony Brook NY 11794 USA

ISBN: (纸本)9781713899921

Whittle index policy is a heuristic to the intractable restless multi-armed bandits (RMAB) problem. Although it is provably asymptotically optimal, finding Whittle indices remains difficult. In this paper, we present Neural-Q-Whittle, a Whittle index based Q-learning algorithm for RMAB with neural network function approximation, which is an example of nonlinear two-timescale stochastic approximation with Q-function values updated on a faster timescale and Whittle indices on a slower timescale. Despite the empirical success of deep Q-learning, the non-asymptotic convergence rate of Neural-Q-Whittle, which couples neural networks with two-timescale Q-learning largely remains unclear. This paper provides a finite-time analysis of Neural-Q-Whittle, where data are generated from a Markov chain, and Q-function is approximated by a ReLU neural network. Our analysis leverages a Lyapunov drift approach to capture the evolution of two coupled parameters, and the nonlinearity in value function approximation further requires us to characterize the approximation error. Combing these provide Neural-Q-Whittle with O(1/k(2/3)) convergence rate, where k is the number of iterations.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Scenario-Based Risk-Sensitive Computations of Equilibria for Two-Person Zero-Sum Games

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 3207-3212页

作者： Rajab, Fat-Hy Omar Shamma, Jeff S. Univ Illinois Grainger Coll Engn Dept Ind & Enterprise Syst Engn Champaign IL 61801 USA

A scenario-based risk-sensitive optimization framework is presented to approximate minimax solutions with high confidence. The approach involves first drawing several random samples from the maximizing variable, then solving a sample-based risk-sensitive optimization problem. This letter derives the sample complexity and the required risk-sensitivity level to ensure a specified tolerance and confidence in approximating the minimax solution. The derived sample complexity highlights the impact of the underlying probability distribution of the random samples. The framework is demonstrated through applications to zero-sum games and model predictive control for linear dynamical systems with bounded disturbances.

关键词： Optimization Complexity theory Probability density function Probability distribution Game theory approximation algorithms Sufficient conditions Stochastic processes Linear programming Indexes minimax MPC probabilistic robustness randomized algorithms risk-sensitive optimization

来源：评论

学校读者我要写书评

暂无评论

A theoretical and empirical study of job scheduling in cloud computing environments: the weighted completion time minimization problem with capacitated parallel machines

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期338卷 429-452页

作者： Cohen, Ilan Reuven Cohen, Izack Zaks, Iyar Bar Ilan Univ Fac Engn Ramat Gan Israel Technion Israel Inst Technol Fac Ind Engn & Management Haifa Israel

We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. In our setting, the processed jobs may be of varying duration, require different resources, and be of unequal importance (weight). Each server (machine) can process multiple concurrent jobs up to its capacity. We study heuristic approaches with provable approximation guarantees and offer an algorithm that prioritizes the jobs with the smallest volume-by-weight ratio. We bound the algorithm's approximation ratio using a decreasing function of the ratio between the highest resource demand of any job and the server's capacity. Thereafter, we create a hybrid, constant approximation algorithm for two or more machines. We also develop a constant approximation algorithm for the case of a single machine. Via a numerical study and a mixed-integer linear program of the problem, we demonstrate the performance of the suggested algorithm with respect to the optimal solutions and alternative scheduling methods. We show that the suggested scheduling method can be applied to both offline and online problems that may arise in real-world settings. This research is the first, to the best of our knowledge, to propose a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines.

关键词： Scheduling Capacitated machines Cloud computing Parallel machines approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：