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

POLYNOMIAL TIME approximation SCHEMES FOR THE TRAVELING REPAIRMAN AND OTHER MINIMUM LATENCY PROBLEMS

SIAM JOURNAL ON COMPUTING 2021年第5期50卷 1580-1602页

作者： Sitters, Rene Vrije Univ Dept Econometr & Operat Res NL-1081 HV Amsterdam Netherlands Ctr Wiskunde & Informat CWI NL-1090 GB Amsterdam Netherlands

We give a polynomial time approximation scheme for the weighted traveling repairman problem (TRP) in the Euclidean plane, on trees, and on planar graphs. This improves upon the quasi-polynomial time approximation schemes for the unweighted TRP in the Euclidean plane and trees and on the 3.59-approximation for planar graphs. The algorithms are based on a new decomposition technique that reduces the approximation of weighted TRP to instances for which we may restrict ourselves to solutions that are the concatenation of only a constant number of traveling salesman problem paths. A similar reduction applies to many other problems with an average completion time objective. To illustrate the strength of this approach, we apply the same technique to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, 1 vertical bar prec vertical bar Sigma w(j)C(j), and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known 3/2-approximation for this problem.

关键词： minimum latency tour traveling repairman approximation algorithms interval orders total completion time

来源：评论

学校读者我要写书评

暂无评论

Approximability of Edge-Vertex Domination in Unit Disk Graphs 2nd

Approximability of Edge-Vertex Domination in Unit Disk Gra...

引用

2nd International Conference on Applied algorithms, ICAA 2025

作者： Singireddy, Vishwanath R. Basappa, Manjanna Geethanjali College of Engineering and Technology Cheeryala Keesara Hyderabad501301 India National Institute of Technology Karnataka Surathkal Mangaluru575025 India

ISBN: (纸本)9783031845420

Given an undirected graph G=(V,E), a vertex v∈V is edge-vertex (ev) dominated by an edge e∈E if v is either incident to e or incident to an adjacent edge of e. A set Sev⊆E is an edge-vertex dominating set (referred to as ev-dominating set and in short as EVDS) of G if every vertex of G is ev-dominated by at least one edge of Sev. The minimum cardinality of an ev-dominating set is the ev-domination number. The edge-vertex dominating set problem is to find a minimum ev-domination number. The EVDS problem finds applications in handling security issues in the communication network by identifying a minimum number of critical edges to implement additional security measures to safeguard key components of the network. In this paper, we prove that this problem admits a polynomial-time approximation scheme in unit disk graphs. We also give a simple 5-factor linear-time approximation algorithm. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

An approximation Algorithm for Unrelated Parallel Machine Scheduling Under TOU Electricity Tariffs

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2021年第2期18卷 743-756页

作者： Pei, Zhi Wan, Mingzhong Jiang, Zhong-Zhong Wang, Ziteng Dai, Xu Zhejiang Univ Technol Coll Mech Engn Hangzhou 310023 Peoples R China Northeastern Univ Sch Business Adm Shenyang 110167 Peoples R China Northeastern Univ Inst Behav & Serv Operat Management Shenyang 110167 Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang 110167 Peoples R China Northern Illinois Univ Dept Ind & Syst Engn De Kalb IL 60115 USA

In an era of sustainable development, considerable emphasis has been put onto energy saving, environment friendly, and social welfare as well as productivity in the manufacturing sector. In this work, an unrelated parallel manufacturing setting with time-of-use (TOU) electricity price is explored, with an aim to reduce the electricity cost and increase productivity simultaneously. A nonlinear mathematical programming model is formulated to exploit the special structure of the scheduling problem, where the quadratic constraints are reformulated as second-order-cone (SOC) constraints, and several tailored cutting planes are introduced to further tighten the feasible region of the problem. Then, the original scheduling problem is transformed into several single-machine scheduling problems with TOU electricity price, which could be relaxed as a single-objective programming problem, and it could be solved rapidly via commercial solvers, such as CPLEX. Based on the optimal solution of the relaxed problem, an approximate algorithm is proposed, where a special rounding technique is employed to assign jobs to the unrelated parallel machines in a local search manner. Furthermore, a lower bound model is constructed by eliminating the nonpreemption constraint, and an iteration-based algorithm is devised to obtain the optimal solution of the lower bound problem. Meanwhile, a dispatch rule-based approach is proposed to provide an upper bound of the scheduling problem with TOU constraint. In the numerical analysis section, the proposed approximate algorithm is validated through extensive testing on various scales of instances, different emphasis on productivity and electricity price, and under two typical TOU electricity pricing policies. It is observed that the gap between the proposed approximate algorithm and CPLEX is mostly within 4%, and the lower/upper bound methods could obtain a relaxed/feasible solution within 0.01 s. Note to Practitioners-Energy saving together with prod

关键词： Job shop scheduling Parallel machines approximation algorithms Single machine scheduling Pricing Productivity Approximate algorithm cutting plane lower bound second-order-cone (SOC) time-of-use (TOU) unrelated parallel machine scheduling

来源：评论

学校读者我要写书评

暂无评论

AirNN: A Featherweight Framework for Dynamic Input-Dependent approximation of CNNs

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2021年第10期40卷 2090-2103页

作者： Hemmat, Maedeh San Miguel, Joshua Davoodi, Azadeh Univ Wisconsin Dept Elect & Comp Engn 1415 Johnson Dr Madison WI 53706 USA

In this work, we propose AirNN, a novel framework which enables dynamic approximation of an already-trained convolutional neural network (CNN) in hardware during inference. AirNN enables input-dependent approximation of the CNN to achieve energy saving without much degradation in its classification accuracy at runtime. For each input, AirNN uses only a fraction of the CNN's weights based on that input (with the rest remaining 0) to conduct the inference. Consequently, energy saving is possible due to fewer number of fetches from off-chip memory as well as fewer multiplications for majority of the inputs. To achieve per-input approximation, we propose a clustering algorithm that groups similar weights in the CNN based on their importance, and design an iterative framework that decides dynamically how many clusters of weights should be fetched from off-chip memory for each individual input. We also propose new hardware structures to implement our framework on top of a recently proposed FPGA-based CNN accelerator. In our experiments with popular CNNs, we, on average, show 49% energy saving with less than 3% degradation in classification accuracy due to doing inference with only a fraction of the weights for the majority of the inputs. We also propose a greedy interleaving scheme, implemented in hardware, in order to improve the performance of the iterative procedure and compensate for its latency overhead.

关键词： Hardware Clustering algorithms approximation algorithms Neurons Degradation Neural networks Inference algorithms Approximate computation early termination input-dependent approximation low-energy design neural network accelerators

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation of Two-Terminal Networks Reliability Polynomials Using Cubic Splines

引用

IEEE TRANSACTIONS ON RELIABILITY 2021年第3期70卷 1193-1203页

作者： Cristescu, Gabriela Dragoi, Vlad-Florin Aurel Vlaicu Univ Arad Dept Math & Comp Sci Arad 310032 Romania

In this article, two new techniques of approximation of the reliability of a two-terminal network are developed based on the constructive theory of functions and related methods. Two methods of generating an approximation cubic spline are used: Lagrange-type interpolation procedures and Bernstein approximation operator. A possibility of minimizing the total error of approximation, based on keeping some properties invariant, is described in case of a large class of pairs of dual two-terminal networks. Simulations are included, showing that the error of approximation is negligible in case of some special initial data.

关键词： Reliability Computer network reliability Telecommunication network reliability Splines (mathematics) Reliability theory approximation algorithms Integrated circuit reliability Bernstein polynomial cubic spline approximation interpolation reliability polynomial two-terminal network (2TN)

来源：评论

学校读者我要写书评

暂无评论

SlowBERT: Slow-down Attacks on Input-adaptive Multi-exit BERT 61

SlowBERT: Slow-down Attacks on Input-adaptive Multi-exit BER...

引用

61st Annual Meeting of the the Association-for-Computational-Linguistics (ACL)

作者： Zhang, Shengyao Pan, Xudong Zhang, Mi Yang, Min Fudan Univ Sch Comp Sci Shanghai Peoples R China

ISBN: (纸本)9781959429623

For pretrained language models such as Google's BERT, recent research designs several input-adaptive inference mechanisms to improve the efficiency on cloud and edge devices. In this paper, we reveal a new attack surface on input-adaptive multi-exit BERT, where the adversary imperceptibly modifies the input texts to drastically increase the average inference cost. Our proposed slow-down attack called SlowBERT integrates a new rank-and-substitute adversarial text generation algorithm to efficiently search for the perturbation which maximally delays the exiting time. With no direct access to the model internals, we further devise a time-based approximation algorithm to infer the exit position as the loss oracle. Our extensive evaluation on two popular instances of multi-exit BERT for GLUE classification tasks validates the effectiveness of SlowBERT. In the worst case, SlowBERT increases the inference cost by 4.57x, which would strongly hurt the service quality of multi-exit BERT in practice, e.g., increasing the real-time cloud services' response time for online users.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Successive Convex approximation for Nonconvex Economic Dispatch in Smart Grid

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2021年第12期17卷 8288-8298页

作者： Xu, Bowen Guo, Fanghong Zhang, Wen-An Wang, Wei Wen, Changyun Li, Zhengguo Zhejiang Univ Technol Dept Automat Hangzhou 310023 Peoples R China Beihang Univ Sch Automat Sci & Elect Engn Beijing 100191 Peoples R China Beihang Univ Beijing Adv Innovat Ctr Big Data & Brain Comp Beijing 100191 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore Agcy Sci Technol & Res SRO Dept Inst Infocomm Res Singapore 138632 Singapore

This article presents a distributed consensus-based successive convex approximation (DSCA) algorithm to solve nonconvex nondifferentiable economic dispatch (ED) problems. The ED model formulated incorporates generation constraints, valve-point effects, and multiple fuel types. A perturbation technique enables the proposed DSCA to tackle such a nondifferentiable and nonconvex optimization, which paves the way to solving more complicated optimization problems that occur in practical applications. The local generation constraint is taken care by a local surrogate convex optimization directly. The global equality constraint is handled based on a consensus protocol, where the local generation-demand mismatch among all dispatchable generators (DGs) is shared in a distributed manner. As a result, the power distribution of DGs is updated, and the generation cost is minimized. Several case studies show that the proposed DSCA algorithm can achieve superior ED solutions and computational efficiency over existing nonconvex optimization algorithms.

关键词： approximation algorithms Smart grids Perturbation methods Heuristic algorithms Fuels Informatics Generators Distributed algorithm economic dispatch (ED) nonconvex optimization smart grid successive convex approximation (SCA)

来源：评论

学校读者我要写书评

暂无评论

approximation Results for Makespan Minimization with Budgeted Uncertainty

引用

THEORY OF COMPUTING SYSTEMS 2021年第6期65卷 903-915页

作者： Bougeret, Marin Jansen, Klaus Poss, Michael Rohwedder, Lars Univ Montpellier CNRS LIRMM Montpellier France Univ Kiel Dept Comp Sci D-24098 Kiel Germany

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to Bertsimas et al. (Math. Program. 98(1-3), 49-71 2003), once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of 2 - epsilon for the case of unrelated machines.

关键词： Makespan minimization Robust optimization approximation algorithms EPTAS Parallel machines Unrelated machines

来源：评论

学校读者我要写书评

暂无评论

TOWARD TIGHT approximation BOUNDS FOR GRAPH DIAMETER AND ECCENTRICITIES

引用

SIAM JOURNAL ON COMPUTING 2021年第4期50卷 1155-1199页

作者： Backurs, Arturs Roditty, Liam Segal, Gilad Williams, Virginia Vassilevska Wein, Nicole MIT 77 Massachusetts Ave Cambridge MA 02139 USA Bar Ilan Univ Comp Sci Tel Aviv Israel Bar Ilan Univ Comp Sci Ramat Gan Israel MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA MIT EECS 77 Massachusetts Ave Cambridge MA 02139 USA

Among the most important graph parameters is the diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the diameter can be approximated within a multiplicative factor of 3/2 in (O) over tilde (m(3/2)) time. Furthermore, Roditty and Vassilevska W. [Proceedings of STOC '13, New York, ACM, 2013, pp. 515--524] showed that unless the strong exponential time hypothesis (SETH) fails, no O(n(2-epsilon)) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O(m(3/2 -epsilon)) time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters is the eccentricities. The eccentricity of a vertex v is the distance between v and the farthest vertex from v. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the eccentricities of all vertices can be approximated within a factor of 5/3 in O (m(3/2)) time and Abboud, Vassilevska W., and Wang [Proceedings of SODA 2016, Arlington, VA, 2016, pp. 377--391] showed that no O(n(2-epsilon)) algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no O(m(3/2-epsilon)) algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the eccentricities. This is the first lower bound

关键词： graph diameter approximation algorithms fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

Electromagnetic Transient Analysis of Transmission Line Based on Rational Krylov approximation

引用

IEEE TRANSACTIONS ON POWER DELIVERY 2021年第5期36卷 2913-2920页

作者： Mouhaidali, Amjad Tromeur-Dervout, Damien Chadebec, Olivier Guichon, Jean-Michel Silvant, Sebastien SuperGrid Inst F-69628 Villeurbanne France Univ Claude Bernard Lyon 1 Univ Lyon Inst Camille Jordan CNRSUMR 5208 F-69622 Villeurbanne France Univ Grenoble Alpes G2Elab Grenoble INP CNRS F-38000 Grenoble France

This paper shows a comparison between Vector fitting and rational Krylov fitting techniques for the determination of rational models concerning the fitting accuracy, the computational performances and the model order. Primarily, the mathematics behind the second technique are presented. It should be noted that rational Krylov fitting have never been used in transmission line modeling. A new procedure is proposed to use rational Krylov fitting instead of vector fitting in the universal line model (ULM). Furthermore, it is demonstrated that this procedure has several advantages over the traditional one. Two illustrative examples involving a transmission system are presented for validation of the new procedure.

关键词： Computational modeling Transmission line matrix methods Admittance Power transmission lines Convergence Mathematical model approximation algorithms Electromagnetic transient frequency depend- ency rational krylov approximation vector fitting transmission line model passivity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：